洛谷 P1208混合牛奶 题解

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

一道贪心算法不是很明显的题目,其实一般的递推也可以做。


 

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

话不多说,上代码:

 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 }

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

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6