旅行传送门：P3619 魔法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
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
输入输出样例
输入 #11 2 13 1 -9 5 -3输出 #1
+1s
说明/提示
对于20%的数据，n≤10
对于100%的数据，n≤100,000,Z≤10，ti,T≤100,000，−100,000≤bi≤100,000
解题思路
(这题的算法标签应该加个暴力)
初次审题，直觉告诉我们应该先选择bi较大的任务，因为bi越大，剩余的T就越大，能完成的任务就越多（就越有机会续1s），若如此做，那你可以取得91分的好成绩。
那究竟是哪出问题了呢？以一组数据举例：
输入1 3 100 27 -19 91 -39输出
42 -5
+1s
而照我们之前的方法，这里的输出则为“-1”。此时此刻，相信细心的读者此时已经发现端倪了，按照之前的策略：我们先完成第三组任务，再完成第一组，最后再完成第二组，但第一组任务完成后的时间T = 76 < 91,续命失败；但我们换一种思路，先完成第三组，再完成第二组，最后再干第一组，结果与刚才恰恰相反。
那我们应该怎么做才能得到最优解呢？可以这样想：我们将每个任务的ti视为一个阈值，bi为完成任务后付出的代价，有的任务可能它付出的代价很大，但它的阈值却很低，而有的可能付出的代价很小，但阈值却高不可攀，因此如果我们一昧地追求付出的代价最小，可能就会错过一些本该可以完成的任务。像刚才的例子中，若是自作聪明地先完成了阈值和代价都较小的任务一，就会因为达不到任务二过高的阈值而得出错误的答案。
我们设第i个任务的阈值为ti，代价为bi，我们设第j个任务的阈值为tj，代价为bj，若出现上述情况，我们可以得到下式：
T + bi > tj,
T + bj < ti.
化简得：ti + bi > tj + bj ，以此作为排序标准，完美收官。
AC代码
1 #include <bits/stdc++.h>
2 #define FOR(i, j, k) for (int i = (j); i <= (k); i++)
3 #define MAXN 100000 + 10
4
5 struct node
6 {
7 int ti, bi;
8 } a[MAXN];
9
10 inline bool cmp(node a, node b)
11 {
12 return a.ti + a.bi > b.ti + b.bi;
13 }
14
15 int read()
16 {
17 int x = 0, f = 1;
18 char ch = getchar();
19 while (ch < '0' || ch > '9')
20 {
21 if (ch == '-')
22 f = -1;
23 ch = getchar();
24 }
25 while (ch >= '0' && ch <= '9')
26 {
27 x = x * 10 + ch - '0';
28 ch = getchar();
29 }
30 return x * f;
31 }
32
33 int main(int argc, char const *argv[])
34 {
35 int z = read();
36 while (z--)
37 {
38 int n = read(), t = read(), flag = 0;
39 FOR(i, 1, n)
40 a[i].ti = read(), a[i].bi = read();
41 std::sort(a + 1, a + n + 1, cmp);
42 FOR(i, 1, n)
43 {
44 if (t > a[i].ti)
45 t += a[i].bi;
46 else
47 {
48 flag = 1;
49 break;
50 }
51 //保证T在任何时刻都大于0.
52 if (t <= 0)
53 {
54 flag = 1;
55 break;
56 }
57 }
58 if (flag)
59 printf("-1s\n");
60 else
61 printf("+1s\n");
62 }
63 return 0;
64 }
View Code