[文章目录]
Description
每天早晨，约翰的N(1≤N≤25000)头奶牛都排成一列，逐一挤奶．为了提高挤奶的速率，约翰把整个挤奶过程划分成两道工序，每头牛都得连续地完成这些挤奶工序．奶牛们一个接一个地进入挤奶的牛棚，约翰负责实行第一道工序，第二道工序则让他的好友萝卜帮助完成．并且，如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前． 约翰发现，如果奶牛们按某种顺序排队进行挤奶，那么可能会在排队等待上多花很多的时间．比方说，如果约翰要花很长时间才能完成某头奶牛挤奶时的第一道工序，那么萝卜可能会有一段时间没有事做．当煞，如果约翰的工作完成得太快，萝}、面前就会有很多奶牛排起长队． 请你帮助约翰计算一下，如果按照最优的排队方式，最少需要多少时间才能把所有奶牛都挤过奶．对于每头奶牛，我们都知道在她身上完成第一道工序所需的时间Ai，以及完成第二道工序的时间Bi. 1≤Ai，Bi≤20000.
看题解了。。。
i,j两个牛，先i后j的时间为ai+max(bi,aj)+bj=ai+bi+aj+bj-min(bi,aj)
对于x和y，按照min(ax,by) min(ay,bx)从大到小排序。（这个东西居然满足如果x>y y>z => x>z）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
struct node
{
int a,b;
}a[25100];
bool cmp(node x,node y){return min(y.a,x.b)>min(x.a,y.b);}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].a,&a[i].b);
sort(a+1,a+n+1,cmp);
long long A=0,B=0;
for(int i=1;i<=n;++i)
{
A+=a[i].a;
if(A>B) B=A+a[i].b;
else B+=a[i].b;
}
printf("%lld",B);
return 0;
}