洛谷 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 }

 其他洛谷題解可到個人主頁來看。