USACO Section1.3 Mixing Milk 解题报告

　　　　milk解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　我是牛奶制造商，我一天需要N加仑的牛奶，总共有M个农民可以供给我。
　　这M个农民的信息共M行，第i个农民有num[i]加仑牛奶，每加仑价格为price[i]。
　　求我买够牛奶所需的最少钱数。
　　数据保证，农民生产的牛奶总数一定是够的。
【数据范围】
　　0<=N<=2,000,000
　　0<=M<=5,000
　　0<=price[i]<=1,000
　　0<=num[i]<=2,000,000
【输入样例】
　　100 5
　　5 20
　　9 40
　　3 10
　　8 80
　　6 30
【输出样例】
　　630
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　排序一下，贪心即可。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　一遍AC。
　　顺带复习了下类的运算符号重载。

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

 /*

 ID: icedrea1

 PROB: milk

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 struct Farmer

 {

     int price;

     int num;

     friend bool operator<(Farmer const &x,Farmer const &y) { return x.price<y.price; }

 };

 int N,M;

 Farmer F[+maxm];

 void qsort(int l,int r)

 {

     if(l>=r) return;

     int i=l,j=r;

     Farmer x=F[(l+r)>>];

     while(true)

     {

         while(F[i]<x) ++i;

         while(x<F[j]) --j;

         if(i>j) break;

         swap(F[i],F[j]);

         ++i; --j;

     }

     qsort(l,j); qsort(i,r);

 }

 int main()

 {

     ifstream in("milk.in");

     ofstream out("milk.out");

     in>>N>>M;

     for(int i=;i<=M;++i) in>>F[i].price>>F[i].num;

     qsort(,M);

     int cost=;

     for(int i=;N && i<=M;++i)

     {

         int num=min(N,F[i].num);

         N-=num; cost+=F[i].price*num;

     }

     out<<cost<<endl;

     in.close();

     out.close();

     return ;

 }

巴特西

USACO Section1.3 Mixing Milk 解题报告

最新文章

热门文章