USACO-Section1.4 Mixing Milk （贪心算法）

2017-5-27

题目描述

从拥有不同单价和库存牛奶的M个农场主手里买数量为N的牛奶的最小支出

解答

每次都选择单价最小的

代码

/* ID: 18795871 PROG: milk LANG: C++ */ #include<iostream> #include<fstream> #include<cstdlib> using namespace std;const int N = 5000;ifstream fin("milk.in"); ofstream fout("milk.out");struct ll{int pri,num; }x[N+1];int cmp(const void *a,const void *b){struct ll *k1=(struct ll*)a;struct ll *k2=(struct ll*)b;if (k1->pri==k2->pri) return k1->num-k2->num;return k1->pri-k2->pri; }int main() {int i,n,m;fin>>n>>m;for (i=1;i<=m;i++){fin>>x[i].pri>>x[i].num;}qsort(x+1,m,sizeof(x[0]),cmp);int sum=0;for (i=1;i<=m;i++){int r=min(n,x[i].num);sum+=r*x[i].pri;n-=r;if (n<=0) break;}fout<<sum<<endl;return 0; }

简单的贪心算法吧！每次选取单价最小的那个就OK了！我更喜欢用sort排序！

/* ID: 18795871 PROG: milk LANG: C++ */ #include<iostream> #include<fstream> #include<algorithm> using namespace std;ifstream fin("milk.in"); ofstream fout("milk.out");const int N = 5000; int n,m;struct nn{int p,a; }x[N+1];bool cmp(struct nn t1,struct nn t2){return t1.p<t2.p; }int main(){while (fin>>n>>m){for (int i=0;i<m;i++){fin>>x[i].p>>x[i].a;}sort(x,x+m,cmp);int sum=0;for (int i=0;i<m;i++){int cnt=min(x[i].a,n);sum+=cnt*x[i].p;n-=cnt;if (n<=0) break;}fout<<sum<<endl;}return 0; }

总结

以上是生活随笔为你收集整理的USACO-Section1.4 Mixing Milk （贪心算法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。