@Junlier
2018-08-31T22:11:46.000000Z
字数 914
阅读 1924
贪心
有一篇好题解,我就懒得推式子了,毕竟打到电脑上还是很难的
牛逼题解传送门
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 20050
using namespace std;
const int Inf=1e9;
int T,n;
struct DC{
int le,ri;
}ljl[N];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il int cmp(rg const DC &a,rg const DC &b)
{
return min(a.le,b.ri)<min(b.le,a.ri);
}
int main()
{
T=read();
while(T--)
{
n=read();
for(rg int i=1;i<=n;++i)
ljl[i]=(DC){read(),read()};
sort(ljl+1,ljl+n+1,cmp);
rg lst ans=ljl[1].le+ljl[1].ri;
rg lst tot=ljl[1].le;
for(rg int i=2;i<=n;++i)
{
tot+=ljl[i].le;
ans=max(ans,tot)+ljl[i].ri;
}
cout<<ans<<endl;
}
return 0;
}
挺难想的,毕竟我推了近一个小时的式子