Part2.5 P2123 皇后游戏 【贪心、思维】

原题链接：P2123 皇后游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

思路：证明题解：题解 P2123 【皇后游戏】 - TA123 的博客 - 洛谷博客 (luogu.com.cn)

实现：

 1 #include
 2 using namespace std;
 3 //#define mod 1000000007
 4 typedef long long ll;
 5 struct node
 6 {
 7     ll a,b,d;
 8 }v[20005];
 9 bool cmp(struct node e1,struct node e2)
10 {
11     if(e1.d*e2.d>0)
12     {
13         if(e1.d<0&&e2.d<0) return e1.a<e2.a;
14         if(e1.d>0&&e2.d>0) return e1.b>e2.b;
15         //return e1.d
16     }
17     else return e1.d<e2.d;
18 }
19 int main()
20 {   
21     int T;
22     scanf("%d",&T);
23     while(T--)
24     {
25         int n;
26         scanf("%d",&n);
27         for(int i=1;i<=n;i++)
28         {
29             scanf("%lld%lld",&v[i].a,&v[i].b);
30             v[i].d=v[i].a-v[i].b;
31         }
32         sort(v+1,v+1+n,cmp);
33         ll last=v[1].a+v[1].b,sum=v[1].a;
34         for(int i=2;i<=n;i++)
35         {
36             sum+=v[i].a;
37             last=max(last,sum)+v[i].b;
38         }
39         printf("%lld\n",last);
40     }
41     return 0;
42 }