/* ID:tianlin2 PROG:milk LANG:C++ */ #include <iostream> #include <cstdlib> #include <fstream> using namespace std; typedef struct milk milk; struct milk{ int mon; int wei; }; //最大農民數 milk m[5000]; int moncmp(const void *va,const void *vb) { milk *a,*b; a=(milk*)va; b=(milk*)vb; if(a->mon>b->mon) return 1; if(a->mon<b->mon) return -1; return 0; } int main() { ofstream fout("milk.out"); ifstream fin("milk.in"); int we,cfar,cmon=0,cwei=0; fin>>we>>cfar; for(int i=0;i!=cfar;++i) fin>>m[i].mon>>m[i].wei; qsort(m,cfar,sizeof(milk),moncmp); for(int i=0;i!=cfar;++i) { cwei+=m[i].wei; if(cwei<=we) cmon+=m[i].wei*m[i].mon; //考慮了多出的情況 else { cmon=cmon+m[i].wei*m[i].mon-(cwei-we)*m[i].mon; cwei=we; } if(cwei==we) break; } fout<<cmon<<endl; //system("pause"); return 0; }

利用了qsort先把m按照單價的大小升序排列,接下來就好辦了!從最低的價格開始算起!

?

官方給出的優秀算法:

#include <fstream> #define MAXPRICE 1001 using namespace std; int main() { ifstream fin ("milk.in"); ofstream fout ("milk.out"); unsigned int i, needed, price, paid, farmers, amount, milk[MAXPRICE][2]; paid = 0; fin>>needed>>farmers; for(i = 0;i<farmers;i++){ fin>>price>>amount; milk[price][0] += amount; } for(i = 0; i<MAXPRICE && needed;i++){ if(needed> = milk[i][0]) { needed -= milk[i][0]; paid += milk[i][0] * i; } //判斷此價格點是否有奶供應 else if(milk[i][0]>0) { paid += i*needed; needed = 0; } } fout << paid << endl; return 0; }

很巧妙的省去了排序,直接定義一個價格i,歷遍所有價格,看此價格點處是否有奶供應!

轉載于:https://www.cnblogs.com/cyxcw1/archive/2010/02/21/3051337.html

總結

以上是生活随笔為你收集整理的Mixing Milk(USACO)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。