洛谷 P1208混合牛奶 题解

题目传送门

一道贪心算法不是很明显的题目,其实一般的递推也可以做。(逻辑较为严密即可)


 

大体思路:肯定优先购买单价最低的奶农的牛奶,那么就需要先根据牛奶单价进行排序,这里用结构体会更好一点。之后在从前往后一个一个枚举,直至购买的牛奶数量达到要求即可。

话不多说,上代码:

 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 }

 其他洛谷题解可到个人主页来看。

热门相关:纯阳真仙   网游之逆天飞扬   霸皇纪   寂静王冠   大神你人设崩了