一道贪心算法不是很明显的题目,其实一般的递推也可以做。
大体思路:肯定优先购买单价最低的奶农的牛奶,那么就需要先根据牛奶单价进行排序,这里用结构体会更好一点。之后在从前往后一个一个枚举,直至购买的牛奶数量达到要求即可。
话不多说,上代码:
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 }
标签:洛谷,牛奶,weight,int,题解,price,单价,P1208,sum From: https://www.cnblogs.com/zhangqixun/p/17067843.html