[USACO1.3]混合牛奶 Mixing Milk

【timegate】

https://www.luogu.org/problem/P1208

【解题思路】

先按照单价排序，单价小的在前面； 单价一样的就把产量多的放前面；（我是用结构体做的，排序方便）

2，当还需要采购时（n不为零），我们从当前还需采购值开始，挨个减一，总价钱加上当前最小单价，当这头牛产量为零（不能再从它购买时），换一头牛（数组加一），直到购买完（n=0）为止。

3，输出总价钱，等待评测，然后AC;

【code】

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;  5 int n,ans=-1<<30,sum;  6 struct Node{  7     int x;  8     int y;  9 }a[100005]; 10 bool cmp(const Node &a,const Node &b){ 11     if(a.x==b.x)return a.y>b.y; 12     return a.x<b.x; 13 } 14 int main(){ 15     //freopen("3028.in","r",stdin); 16     //freopen("3028.out","w",stdout);
17     scanf("%d",&n); 18     int s,t; 19     for(register int i=1;i<=n;i++){ 20         scanf("%d%d",&s,&t); 21         a[i].x=s; 22         a[i+n].x=t; 23         a[i].y=1; 24         a[i+n].y=-1; 25  } 26     sort(a+1,a+n*2+1,cmp); 27     for(register int i=1;i<=n*2;i++){ 28         sum+=a[i].y; 29         ans=max(ans,sum); 30  } 31     printf("%d\n",ans); 32     return 0; 33 }