USACO - 1.3.1 - Mixing Milk

 

转载请注明出处

摘要：贪心

一. 题目翻译

1. 描述：

          由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助梅丽乳业找到最优的牛奶采购方案。

          梅丽乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天梅丽乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

          给出梅丽乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

          注：每天所有奶农的总产量大于梅丽乳业的需求量。

2. 格式：

          PROGRAM NAME: milk

          INPUT FORMAT: file milk.in

 

          第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数；M,(0<= M<=5,000)是提供牛奶的农民个数。

          第 2 到 M+1 行:每行二个整数:Pi 和 Ai。

          Pi(0<= Pi<=1,000) 是农民 i 的牛奶的价格。

          Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。

          OUTPUT FORMAT:file milk.out

          单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用

3. SAMPLE：

          SAMPLE INPUT:

          100 5

           5 20

 9 40

 3 10

 8 80

 6 30           

          SAMPLE OUTPUT:

      630

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          贪心算法。将所有牛奶按价格升序排列，然后从低到高买入直到达到目标数量。

2. 具体实现（具体实现过程中出现的问题）：

          参考代码，注意排序使用Arrays.sort()方法。

三.  代码

/*
ID: fightin1
LANG: JAVA
TASK: milk
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class milk {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			Scanner in = new Scanner(new BufferedReader(new FileReader("milk.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("milk.out")));
			int total = in.nextInt(); //需要牛奶数量的总数
			int num = in.nextInt(); // 奶农的数目
			milker[] milkers = new milker[num];
			for (int i=0;i<num;i++){
				int price = in.nextInt();
				int amount = in.nextInt();
				milkers[i] = new milker(price,amount);
			}
			Arrays.sort(milkers,new cmp());//奶农数组排序
			
			int index = 0;
			int result = 0;
			while (total>0){ //从单价小的开始取的，知道取到总量结束
				if (total>milkers[index].amount){
					result = result + milkers[index].amount*milkers[index].price;
					total = total - milkers[index].amount;
					index ++;
				} else {
					result = result + total*milkers[index].price;
					total = 0;
					index++;
				}
			}
			pw.println(result);
			pw.close();
			in.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

//奶农类的Comparator，用于奶农的排序
class cmp implements Comparator<milker> {
	@Override
	public int compare(milker o1, milker o2) {
		// TODO Auto-generated method stub
		if (o1.price > o2.price){
			return 1;
		} else if (o1.price == o2.price){
			return 0;
		} else {
			return -1;
		}
	}
}

//奶农类
class milker {
	int price; //牛奶单价
	int amount; //牛奶数量
	
	public milker(int price , int amount) {
		this.price = price;
		this.amount = amount;
	}
}