Description
到了学期末，在幼儿园工作的刘老师要为自己所带班级的小朋友分发糖果。刘老师的班上共有n名小朋友，第i位小朋友对糖果的喜爱程度为ai，他在本学期的表现评分为bi。刘老师分配糖果的方法如下：
以某个顺序安排这n位小朋友排成一排，刘老师从头到尾逐一分配糖果。队伍中的第i位小朋友至少获得的糖果数量为前i位小朋友对糖果的喜爱程度之和。由于第i位小朋友可以看见第i−1位小朋友获得的糖果数量，为了不让第i位小朋友觉得不公平，刘老师保证第i位小朋友获得的糖果不少于第i−1位小朋友。在为第i位小朋友分配完糖果后，刘老师将额外再奖励第i位小朋友数量为bi的糖果。
我们设第i位小朋友获得的糖果数量为Ci，形式化地讲：
Ci=a1+b1,i=1
Ci=max(Ci−1,∑ij=1aj)+bi,2≤i≤n
由于预算有限，刘老师希望你能帮她安排这 nn 位小朋友的顺序，使得获得糖果最多的小朋友，所获得的糖果数量尽可能少。
Input
第一行包含一个正整数T，表示测试数据的组数。接下来描述这T组测试数据，每组数组的第一行包含一个正整数n，表示刘老师班上小朋友的数量。每组数据接下来n行中，每行两个正整数，分别为ai和bi。
Output
共T行，每行包含一个整数，表示被分配到最多糖果的那位小朋友最少获得的糖果数量。
Hint
对于所有测试点，1≤n≤5*104，1≤T≤101。
Solution
贪心策略：
return max(a1+b1,a1+a2)+b2<max(a2+b2,a1+a2)+b1;
注意long long和输入输出的lld。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 50005
#define int long long
using namespace std;
struct data{
int a;
int b;
friend bool operator < (data x,data y){
return max(x.a+x.b,x.a+y.a)+y.b<max(y.a+y.b,y.a+x.a)+x.b;
}
}studentt[maxn];
int n,ans,T;
int sum[maxn];
void Clear_J(){
memset(studentt,0,sizeof(studentt));
memset(sum,0,sizeof(sum));
n=ans=0;
}
void init(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&studentt[i].a,&studentt[i].b);
}
}
void Set_Sum(){
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+studentt[i].a;
}
}
void workk(){
sort(studentt+1,studentt+n+1);
Set_Sum();
for(int i=1;i<=n;i++){
ans=max(sum[i],ans)+studentt[i].b;
}
}
signed main(){
scanf("%lld",&T);
for(int i=1;i<=T;i++){
Clear_J();
init();
workk();
printf("%lld
",ans);
}
return 0;
}