Part2.5 P1208 混合牛奶 【贪心】

原题链接：P1208 [USACO1.3]混合牛奶 Mixing Milk - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

思路：结构体存储节点信息，排序后从小到大计算价格指导符合要求为止

评价：贪心

 1 #include
 2 using namespace std;
 3 struct node
 4 {
 5     int p,tot;
 6 }d[2000005];
 7 bool cmp(node a,node b)
 8 {
 9     return a.p<b.p;
10 }
11 int main()
12 {
13     int sum,n,pay=0;
14     scanf("%d %d",&sum,&n);
15     for(int i=0;i)
16     {
17         int p,tot;
18         scanf("%d %d",&d[i].p,&d[i].tot);
19     }
20     sort(d,d+n,cmp);
21     for(int i=0;i)
22     {
23         if(sum>=d[i].tot)
24         {
25             pay+=d[i].tot*d[i].p;
26             sum-=d[i].tot;
27         }
28         else
29         {
30             pay+=d[i].p*sum;
31             sum=0;
32         }
33         if(sum==0) break;
34     }
35     printf("%d",pay);
36     return 0;
37 }