P7700
GuideZombies
·
·
题解
>第 $i$ 个星球有 $a_i$单位燃料，但是从任何星球去那里都要花费 $b_i$ 单位燃料。
$\ \ \ \ $所以不管从哪个星球去星球$x$，所获得的价值都是相等的，考虑贪心。显然地，如果去一个星球$x$所获的价值（即 $a_x - b_x$ ）为负，那肯定不去那个星球，应为去只会让燃料变少。另外，就算这个星球的价值为正，但当前的油量不足以去，那也获得不了这个星球的燃料，所以，应先以 $a_i$ 排序，在进行操作。
略证：
$\ \ \ \ $对于两个星球的信息 $(a_x,b_x)\ ,\ (a_y,b_y)\ ,\ a_x<a_y\ $，若可以去星球 $y$ ，则一定可以去星球 $x$ ,且去过 $x$ 后一定可以去 $y$ (燃料一定会变多)，但可以去 $x$ 星球就不一定可以去 $y$ ，若先考虑 $y$ ，则可能会因当前的燃料不够而跳过 $y$ ，在遍历 $x$ 后，就算当前燃料可以去 $y$ ，也不会再去考虑 $y$ 了。
得证.
$\ \ \ \ $对于去的星球尽量多，只需要将那些 $a = b$ 的星球也考虑到遍历当中，虽然这种星球做不出任何贡献，但可以让访问的星球尽量多。
code:
```
#include <bits/stdc++.h>
using namespace std;
struct node {
int v;//去星球需要的代价
int val;//价值
friend bool operator < (node x, node y) {//重载运算符：代价小的排前面
return x.v < y.v;
}
}star[100010];
int n, m, cnt;
int main() {
cin >> n >> m;
int oil, sum = 1;
for (int i = 1; i <= n; ++i) {
int a, b;
cin >> a >> b;
if (a - b >= 0 && i != m) {
star[++cnt].v = b;
star[cnt].val = a - b;//只将对答案用贡献的星球加入列表
}
if (i == m) oil = a;
}
sort(star + 1, star + cnt + 1);
for (int i = 1; i <= cnt; ++i) {
if (oil >= star[i].v) {
oil += star[i].val;
++sum;
}
else break;//如果当前星球去不了，那以后的肯定都去不了，直接退出循环
}
cout << oil << endl << sum;
return 0;
}
```