usaco题目mixingmilk(milk)及代码解析

《usaco题目mixingmilk(milk)及代码解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。Marry乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。给出Marry乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。注：每天所有奶农的总产量大于Marry乳业的需求量。[编辑]格式PROGRAMNAME:milkINPUT

2、FORMAT:filemilk.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的牛奶制造公司的牛奶数量。OUTPUTFORMAT:filemilk.out单独的一行包含单独的一个整数，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用[编辑]SAMPLEINPUT1005520940310880630[编辑]SAMPL

3、EOUTPUT630很牛逼！！！！利用数组先天排序！#include inta[1001]={}; intmain(){freopen("milk.in","r",stdin);freopen("milk.out","w",stdout);intm,n,price,amount,res=0;scanf("%d%d",&n,&m);for(;m;--m){scanf("%d%d",&price,&amount);a[price]+=amount;}for(m=0;;++m){if(n>a[m]){res+=a[m]*m;n-=a[m];}else{res+

4、=n*m;break;}}printf("%d",res);}、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、#includeusingnamespacestd;intm,n,i,j;intp1[5000],p2[5000];intsum,ans;intmain(){intmax=0;freopen("milk.in","r",stdin);freopen("milk.out","w",stdout);cin>>n>>m;for(i=0;i>p1[i]>>p2[i];for(

5、i=0;ip1[j]){intt=p1[i];p1[i]=p1[j];p1[j]=t;intq=p2[i];p2[i]=p2[j];p2[j]=q;}ans=0;max=0;for(i=0;;i++){if(max+p2[i]