闲话

这个题虽然一眼看出了贪心，但是想不出怎么排序。

大体思路与贪心证明

战争游戏

类似这题，我们最优情况需要把能力筹集完之后再清剿。我们看看哪些怪物能帮助我们最大增加能量呢？肯定是 $b_i - a_i$ 为正的，这些怪物贪心地打，我们就按 $a_i$ 从小到大排。这样我们需要的基础能量就会最小。

重点来了，在积蓄完所有可获取的能量后，面对那些 $b_i - a_i \le 0$ 的怪物我们怎么处理？
运用邻项交换法严谨求解：
设现在有 $2$ 个怪，分别是 $\{a_1 , b_1\}$ 和 $\{ a_2 , b_2 \}$。
当前剩余 $h$ 点能量。
先打 $1$，再打 $2$ 时有 $2$ 个瓶颈：先是打 $1$ 时的 $h \ge a_1$，打完后能量变为 $h - a_1 + b_1$，来到第 $2$ 个瓶颈，$h - a_1 + b_1 \ge a_2$，移项得 $h \ge a_2 + a_1 - b_1$。则获得 $h$ 的综合瓶颈：

再看反过来的情况。同理得：

观察发现，两种打怪方案唯二区别就是第一项 $a_1$ 和 $a_2$，以及第二项末尾 $b_1$ 和 $b_2$。
既然前面已经拿 $a$ 排过了，我们不妨试试用 $b$ 来排。
假设 $b_1 \ge b_2$，第二种方案的第二项得 $a_2 + (a_1 - b_2)$。
等量代换得 $a_1 \ge b_2$。
则第二项为 $a_2 + \text{正数}$，化简第二种方案得 $h = a_1 + a_2 - b_2$。

回看第一种方案，我们验证一下。
先拿出来第一项 $a_1$，有 $a_2 \ge b_2$，推导得 $a_1 \le h$。
再看看第二项。同理，前面假设了 $b_1 \ge b_2$，减去更大的数，结果必然更小，则亦有 $a_1 + a_2 - b_1 \le h$。

既然第一种方案的两个候选值都比第二种方案的 $h$ 小，则无论取哪一个，都有：

证毕。综上所述，按 $b_1 > b_2$ 排列，整体血量开销一定最小。所以扣血的第二组怪兽需要按 $b$ 的降序排列。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
int n;
struct node {
	ll x , y;
	bool operator < (const node &oth) const {
		return x < oth.x;
	}
};
vector < node > p;
struct pt {
	ll x , y;
	bool operator < (const pt &oth) const {
		if (y != oth.y)
			return y > oth.y;
		return x < oth.x;
	}
};
vector < pt > q;

int main () {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		ll a , b;
		cin >> a >> b;
		if (b - a >= 0)
			p.push_back({a , b});
		else
			q.push_back({a , b});
	}
	sort(p.begin() , p.end());
	sort(q.begin() , q.end());
	ll ans = 0 , cnt = 0;
	for (node i : p) {
		if (cnt < i.x) {
			ans += i.x - cnt;
			cnt = i.x;
		}
		cnt += i.y - i.x;
	}
	for (pt i : q) {
		if (cnt < i.x) {
			ans += i.x - cnt;
			cnt = i.x;
		}
		cnt += i.y - i.x;
	}
	cout << ans;
	return 0;
}

大体思路清晰，代码不做冗余解释了。

总结

贪心题一定不要干瞪或者瞎画个草图猜测排序方式，先进行严谨的推导，确保贪心不会假了再去写代码。