【练习】「土」巨石滚滚
「土」巨石滚滚
https://ac.nowcoder.com/acm/problem/53681
题目
题目描述：帕秋莉掌握了一种土属性魔法
她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
输入描述：
输入一个整数T，代表T组数据，每组数据中：
前一行两个整数n , m，表示障碍个数和土球的稳定性
接下来一行两个整数，分别表示障碍的ai和bi
若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)
解析
这道题的题不难看懂，可我还是看错了，没看到要排序。。。
- 题目意思就是排个序使土球尽量有可能撞完所有石头。
所以这道题非常明显就是一道贪心问题，那我们来讨论贪心策略：
- 首先我们知道，贪心肯定贪心在排序上面，我们在排序上面可以怎么贪呢？无非与a和b有关。
- 然后要注意一点就是，我们是先对球损坏a，再修复b，如果损坏了a就使稳定性变成负数了，就结束了。
- 所以我们现在的贪心要素有：a的损坏大小，b的修补大小。
- 在看到这里我们发现，a和b没有大小之分，所以我们在撞了石头之后，稳定性还有可能反而升高了。
所以我们毫无疑问的将可以升高稳定性的排在前面
（为什么不升高稳定性的不能在前面呢？因为如果在连升高的时候都能撞烂了，那降低了之后就更容易烂掉了）。 - ————————————————————分ger线————————————————————
- 然后我们数组就分成了两个部分：前面是稳定性升高（包括不变）的，后面是稳定性降低的。然后我们就要考虑，这两块里面怎么排。
- 也许你会觉得这两块都没啥必要排了，但其实这个排序很重要。
- 稳定性升高内部排序规则：虽然每个都可以让稳定性升高，但是我们还要考虑在升高的过程中这个球会不会烂掉！！
这个时候就可能出现，在某一次损坏下，我们这个球会烂掉，但是假如别的撞后不会烂的球帮它升高之后，就不会撞烂了的情况。
所以：我们的排序就应该有这一点：按照损坏程度大小，从小到大排序（也就是在为下一个球的情况做贡献）。 - 稳定性降低内部排序规则：这个时候我们不应该考虑自己这个球会不会烂掉，因为该烂掉总会烂掉。但我们要保证下一个更不容易烂掉。
所以我说的：不用在乎自己的意思是，如果我的破坏值已经很大了，怎么换都没有意义，一样会烂掉。
然后我说的要为下一个球考虑就是：让下一个的时候，我们的稳定性能更高，也就是这一个的回复值要更大。
所以我们的排序就应该有这一点：按照恢复程度的大小，从大到小排序（让下一个有更多空间去破坏）。
然后就是怎么操作的问题了对吧：
- 我们在这里用到一个方便的就是STL库里面的sort函数。我们这里阔以写一个cmp函数，也可以重载运算符。
- 我在这里是重载运算符，因为这样可以大幅提高排序效率（两个写起来是一样的）。
- 因为我们在这里有两个因素：a的损坏大小，b的修补大小。所以就有四种情况（我们假设在数组里面靠前面的是u，靠后面的是v）。
- <1>假如u，v稳定性都升高，我们按照损坏程度升序排序：
if (a <= b && v.a <= v.b) return a < v.a;
- <2>假如u稳定性升高，v稳定性降低，我们顺序不用变（因为稳定性升高的要在前面）：
if (a <= b && v.a > v.b) return true;
- <3>假如u稳定性降低，v稳定性升高，我们交换顺序（理由同上）：
if (a > b && v.a <= v.b) return false;
- <4>假如u，v稳定性都降低，我们按照修补程度降序排序：
if (a > b && v.a > v.b) return b > v.b;
打代码咯：
- 输入数组。
- 排个序咯。
- 然后循环遍历，判断是否会挂（损坏的时候是否耐久度小于0），用flag标记。
- 看我代码咯~
AC代码
#include <iostream>
#include <algorithm>
#include <cstdbool>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 5e5 + 7;
struct Node {
int a, b;
bool operator < (const Node& v) const {
if (a <= b && v.a <= v.b) return a < v.a;
//如果两个都可以增加，先增加消耗小的（让后面消耗大的回复块有机会）
if (a <= b && v.a > v.b) return true;
if (a > b && v.a <= v.b) return false;
//如果一个可以增加，另一个不可以，就让可以增加的在前面
if (a > b && v.a > v.b) return b > v.b;
//剩下的就是都不能增加的情况，就让回复多的先
}
} stone[MAX];
//全局变量区
int main() {
IOS;
int T; cin >> T;
while (T--) {
ll n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> stone[i].a >> stone[i].b;
sort(stone + 1, stone + 1 + n);
bool flag = true;//flag=1表示石头没散架
for (int i = 1; i <= n && flag; i++)
if (m - stone[i].a < 0) flag = false;
else m -= stone[i].a - stone[i].b;
cout << (flag ? "Yes" : "No") << endl;
}
return 0;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
投递腾讯等公司10个岗位 >
