HDU 1009 FatMouse' Trade

原题：http://acm.hdu.edu.cn/showproblem.php?pid=1009

Problem Description:

 FatMouse准备了M磅的Cat-Food，以便用来跟小Cat交换好吃的JavaBean。

 现在有N个房间，第i个房间有J[i]磅的JavaBean，其交换的筹码是F[i]磅的Cat-Food。

当然，FatMouse还是有很大的选择权的，对任意一个房间，它可以只交换一部分的Cat-Food。

现要求FatMouse以怎样的策略才能获得最多的Cat-Food。

Solution：

贪心入门题，对象数组排序时我用到了Comparator接口，个人在这上面花了点时间。

JAVA 代码（AC）:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	/**
	 * 稻草人
	 * HDU 1009(AC)
	 */
	public static Node[] node = new Node[1001];
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			int mNum = in.nextInt();
			int nNum = in.nextInt();
			
			if(mNum==-1&&nNum==-1)
				break;
			for(int i=0;i<nNum;i++)
			{
				node[i] = new Node();
				node[i].javaBeans = in.nextInt();
				node[i].food = in.nextInt();
				node[i].rex = node[i].javaBeans*(1.0)/node[i].food;
			}
			Arrays.sort(node,0, nNum);
			getAns(mNum,nNum);
		}

	}
	public static void getAns(int m,int n)
	{
		double reSum=0.0;
		for(int i=0;i<n;i++)
		{
			if(node[i].food<=m){
				m-=node[i].food;
				reSum+=node[i].javaBeans;
			}
			else
			{
				reSum+=node[i].javaBeans*(1.0)*m/node[i].food;
				break;
			}
		}
		System.out.printf("%.3f",reSum);
		System.out.println();
	}

}
class Node implements Comparable<Node>
{
	int javaBeans;
	public int getJavaBeans() {
		return javaBeans;
	}
	public void setJavaBeans(int javaBeans) {
		this.javaBeans = javaBeans;
	}
	public int getFood() {
		return food;
	}
	public void setFood(int food) {
		this.food = food;
	}
	int food;
	double rex;
	public double getRex() {
		return rex;
	}
	public void setRex(double rex) {
		this.rex = rex;
	}
	@Override
	public int compareTo(Node o) {
		// 从大到小排序
		if(o.getRex()>this.rex)
			return 1;
		else if(o.getRex()<this.rex)
			return -1;
		else
			return 0;
	}
}