Luogu P3619 魔法【贪心/微扰证明】

题目描述

cjwssb知道是误会之后，跟你道了歉。你为了逗笑他，准备和他一起开始魔法。不过你的时间不多了，但是更惨的是你还需要完成n个魔法任务。假设你当前的时间为T，每个任务需要有一定的限制ti表示只有当你的T严格大于ti时你才能完成这个任务，完成任务并不需要消耗时间。当你完成第i个任务时，你的时间T会加上bi，此时要保证T在任何时刻都大于0，那么请问你是否能完成这n个魔法任务，如果可以，输出+1s，如果不行，输出-1s。

输入输出格式

输入格式：

第一行：一个整数Z，表示有Z个测试点。

对于每个测试点

第一行：一个整数n,T，表示有n个任务,你一开始有T的时间。

接下来n行，每行2个数字，ti与bi

输出格式：

对于每个测试点，输出+1s或者-1s

输入输出样例

输入样例#1：

输出样例#1：

+1s

说明

对于20%的数据，n≤10

对于100%的数据，n≤100,000,Z≤10，ti,T≤100,000，−100,000≤bi≤100,000

By：lantian

观察样例后我们发现，竟然有负数！看起来只能大力贪心了！

大力贪心一番，我们发现我们可以先做所有bi为正的任务，这样我们所拥有的续命时间就会猛增，达到一个人生巅峰！

这部分可以先按ti递增排序，先满足条件的低的任务，步步走上人生巅峰。

bi为正的任务，我们就处理完了。

再来看bi为负的任务，想一想我们好像手足无措、无计可施。不妨考虑一些优雅的、有根据的贪心？

还记得国王游戏吗？那道题我们用到了微扰（邻值交换）的方法，这道题会不会也适用？

什么是微扰？粗糙的理解就是在局部情况下，我们交换两个变量组的值，这里只会改变局部的情况，而整体局面不变。交换后局部情况可能会变得更优或更差，于是我们就可以找出一种排序的根据，再进行贪心便有理有据。关键是交换前后局部情况改变，才能得到正确的关系。

//图片怎么旋转啊！！麻烦各位看官转个头qwq

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<utility>
 4 
 5 using namespace std;
 6 
 7 int T,ti,n,tot,cnt;
 8 struct node{
 9     int t,b;
10 }nega[100050];
11 struct Vergil{
12     int t,b;
13 }posi[100050];
14 
15 bool cmp1(Vergil p,Vergil q)
16 {
17     return p.t<q.t;
18 }
19 
20 bool cmp2(node p,node q)
21 {
22     return p.t+p.b>q.t+q.b;
23 }
24 
25 void clear()
26 {
27     for(int i=1;i<=cnt;i++) nega[i].t=0,nega[i].b=0;
28     for(int i=1;i<=tot;i++) posi[i].t=0,posi[i].b=0;
29     cnt=0,tot=0;
30 } 
31 
32 int main()
33 {
34     scanf("%d",&T);
35     while(T--)
36     {
37         clear();
38         bool flag=false;
39         scanf("%d%d",&n,&ti);
40         for(int i=1;i<=n;i++)
41         {
42             int x=0,y=0;
43             scanf("%d%d",&x,&y);
44             if(y>0) posi[++tot].t=x,posi[tot].b=y;
45             else nega[++cnt].t=x,nega[cnt].b=y;
46         }
47         sort(posi+1,posi+tot+1,cmp1);
48 
49         for(int i=1;i<=tot;i++)
50         {
51             if(ti<=posi[i].t)
52             {
53                 printf("-1s
");
54                 flag=true;
55                 break;
56             }
57             ti+=posi[i].b;
58             if(ti<=0)
59             {
60                 printf("-1s
");
61                 flag=true;
62                 break;
63             }
64         }
65         if(flag) continue;
66         
67         sort(nega+1,nega+cnt+1,cmp2);
68         for(int i=1;i<=cnt;i++)
69         {
70             if(ti<=nega[i].t)
71             {
72                 printf("-1s
");
73                 flag=true;
74                 break;
75             }
76             ti+=nega[i].b;
77             if(ti<=0)
78             {
79                 printf("-1s
");
80                 flag=true;
81                 break;
82             }
83         }
84         if(flag) continue;
85         printf("+1s
");
86     }
87     return 0;
88 }

View Code

注意是严格大于！在这被坑了qwq