自动搬运

查看原文

来自洛谷，原作者为

	GuideZombies All tragedy erased. I see only wonders...

搬运于2025-08-24 22:32:18，当前版本为作者最后更新于2021-07-20 19:20:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\ \ \ \$第一眼还以为是一道最短路的题，知道看到这一句话：

第 $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;
}