Mixing Milk - USACO 1.3

mixingmilk - codetrick

Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.

The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer's limit.
Given the Merry Milk Makers' daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers' requirements.
Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

PROGRAM NAME: milk

INPUT FORMAT

Line 1:	Two integers, N and M. The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers' want per day. The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
Lines 2 through M+1:	The next M lines each contain two integers, Pi and Ai. Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges. Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

SAMPLE INPUT (file milk.in)

100 5  5 20  9 40  3 10  8 80  6 30  

OUTPUT FORMAT

A single line with a single integer that is the minimum price that Merry Milk Makers can get their milk at for one day.

SAMPLE OUTPUT (file milk.out)

630

贪心算法，每次取单价最低的牛奶
http://code.antonio081014.com/2012/09/usaco-mixing-milk.html

public class milk {

    public List<Farmer> list;

    public static void main(String[] args) throws Exception {
        milk main = new milk();
        main.solve();
        System.exit(0);
    }

    public void solve() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("milk.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("milk.out"));
        String[] str = br.readLine().split("\\s");
        int amount = Integer.parseInt(str[0]);
        int N = Integer.parseInt(str[1]);
        list = new ArrayList<Farmer>();
        for (int i = 0; i < N; i++) {
            str = br.readLine().split("\\s");
            int p = Integer.parseInt(str[0]);
            int a = Integer.parseInt(str[1]);
            list.add(new Farmer(p, a));
        }
        Collections.sort(list);
        long sum = 0L;
        for (int i = 0; i < N; i++) {
            if (amount >= list.get(i).amount) {
                sum += ((long) list.get(i).price) * list.get(i).amount;
                amount -= list.get(i).amount;
            }
            else {
                sum += ((long) amount) * list.get(i).price;
                break;
            }
        }
        out.write("" + sum + "\n");
        out.close();
    }

}
class Farmer implements Comparable<Farmer> {
    public int price;
    public int amount;

    public Farmer(int p, int a) {
        this.price = p;
        this.amount = a;
    }

    @Override
    public int compareTo(Farmer o) {
        return this.price - o.price;
    }
}

X. No sort
http://mangogao.com/read/71.html

struct Milk

{

    int price;

    int amount;

    bool mark;

}milk[5000];

int Min(int &a, int &b)

{

    if (a>=b) return b;

    return a;

}

int main()

{

    ifstream fin("milk.in");

    ofstream fout("milk.out");

    int N,M,j,ans(0);

    //输入数据

    fin >> N >> M;

    for (int i = 0; i < M; ++i) fin >> milk[i].price >> milk[i].amount,milk[i].mark=false;

    //假定初始解

    int MinPrice=1001;

    //开始求解

    while (N>0)

    {

        for (int i = 0; i < M; ++i)

        {

            if (milk[i].price<MinPrice && milk[i].mark==false)

            {

                MinPrice=milk[i].price;

                j=i;

            }

        }

        //恢复最小单价

        MinPrice=1001;

        milk[j].mark=true;

        ans += milk[j].price * Min(N, milk[j].amount);

        N-=milk[j].amount;

    }

    fout << ans << endl;

    return 0;

}

X.  Count sort - no sort
http://blog.tomtung.com/2007/02/usaco-mixing-milk/
完全没有必要用O(nlgn)的时间对价格进行快排，因为价格有一个$1000的上界，而且我们知道所有价格都是整数。我们可以用count sort对数组进行排序。我们可以给每一个可用的价格（0..1000）建立一个“盒子”。我们把输入数据存入一个数组，然后扫描每一个农夫，记录他在（0..1000）数组中的下标，此下标就等于他的出价。因此我们可以把出价相同的农夫放入一个链表中。最后，我们从0到1000扫描整个数组，并从链表中取出农夫们的下标。这很容易实现，且时间复杂度为O(n)。

int main() {
    ifstream in("milk.in");
    ofstream out("milk.out");

    int N, M;
    int P[MAXP+1];

    in >> N >> M;
    for (int i = 0; i <= MAXP; i++) P[i]=0;
    for (int i = 0; i < M; i++) {
        int price, amt;
        in >> price >> amt;

         // 我们可以将价格相同的各个农民手中牛奶的总量相加
        // 因为x加仑售价c美分、
        //          y加仑售价c美分
        // 和x+y加仑售价c美分
        //      是一回事
        P[price] += amt;
    }

    // 贪心策略：尽可能多的买售价最低的
    int res = 0;
    for (int p = 0; p<=MAXP && N>0; p++) {
        if (P[p]>0) {
            res+=p*(N<P[p]?N:P[p]);
            N-=P[p];
        }
    }
    out << res << endl;

    in.close();
    out.close();

    return 0;
}

X. Use heap to get current min price
Read full article from mixingmilk - codetrick