8
洛谷 P1208混合牛奶 题解 - 张其勋
source link: https://www.cnblogs.com/zhangqixun/p/17067843.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一道贪心算法不是很明显的题目，其实一般的递推也可以做。
大体思路：肯定优先购买单价最低的奶农的牛奶，那么就需要先根据牛奶单价进行排序，这里用结构体会更好一点。之后在从前往后一个一个枚举，直至购买的牛奶数量达到要求即可。
话不多说，上代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 long long n,m,sum;
4 struct farm{
5 int price,weight;
6 }a[100001];//结构体，price表示单价，weight表示可出售的质量
7 bool cmp(farm x,farm y){
8 return x.price<y.price;
9 }//根据牛奶的单价进行排序
10 int main(){
11 cin>>n>>m;
12 for(int i=1;i<=m;i++){
13 cin>>a[i].price>>a[i].weight;
14 }//输入
15 sort(a+1,a+m+1,cmp);//根据上面的要求进行排序
16 for(int i=1;i<=m;i++){
17 if(a[i].weight>n){//可出售质量超出剩余需求
18 sum+=n*a[i].price;//总和+=剩余需求*单价
19 break;//结束循环
20 }
21 n-=a[i].weight;//剩余需求减去牛奶数量
22 sum+=a[i].price*a[i].weight; //总和+=单价*所有的质量
23 }
24 printf("%d",sum);
25 return 0;
26 }
如果您觉得阅读本文对您有帮助，请点一下“推荐”按钮，您的“推荐”将是我最大的写作动力！欢迎各位转载，但是未经作者本人同意，转载文章之后必须在文章页面明显位置给出作者和原文连接，否则保留追究法律责任的权利。
__EOF__
本文作者： 欢迎来到张其勋的博客 本文链接： https://www.cnblogs.com/zhangqixun/p/17067843.html 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK