思路

省流：这个题是个贪心。

不用说也能看出来，但我唐完了第一眼看成dp了

把题目分成两类：

1.$a[i]\le b[i]$，此时打这个关卡是有收益的，为了让起始精力最小，我们很容易想到按 $a[i]$ （就是代价）从小到大排序。

2.$a[i]>b[i]$，此时打关卡是亏的，我们自然能联想到按回报排序，如果回报相同，我们按代价排序，这样我们就算亏，也能为下一次存下一些精力。此时还有更为严谨的邻项交换法，当前精力 $k$，先打 $i$ 再打 $i+1$ 就要满足 $h-a[i]+b[i]\ge a[i+1]$，移项得 $h\ge a[i]+a[i+1]-b[i]$ 反之就是 $h-a[i+1]+b[i+1]\ge a[i]$，移项得 $h\ge a[i]+a[i+1]-b[i+1]$，因为 $a[i]+a[i+1]$ 是定值，所以 $b$ 越小对 $h$ 的要求就更小，可知按 $b[i]$ 排序。

于是我们可以把数组分成两个分别排序，先处理第一类，在处理第二类，因为第一类先做可以盈利，尽可能使精力需要的最小。

然后我们可以二分也可以模拟，当然我觉得模拟更简洁，每次记录当前精力 $nowA$，如果不足以通过就给 $ans$ 加上差距（即需要补的），同时把 $nowA$ 更新成当前的 $A[i]$（尽可能少补）。 初始时 $nowA=ans=0$。

代码

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 1e5 + 10;

int n;
LL maxv, sum, ans, H;
vector<int> p1, p2;

struct Node {
    LL A, B;
} p[MAXN];

bool cmp1(int a, int b) {
    return p[a].A < p[b].A;
} // 第一类

bool cmp2(int a, int b) {
    return p[a].B != p[b].B ? p[a].B > p[b].B : p[a].A < p[b].A;
} // 第二类

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i].A >> p[i].B;
        maxv = max(maxv, p[i].A);
        if (p[i].A <= p[i].B) 
            p1.push_back(i);
        else
            p2.push_back(i);
    }
    sort(p1.begin(), p1.end(), cmp1);
    sort(p2.begin(), p2.end(), cmp2);
    for (int k : p1) {
        if (H < p[k].A)
            ans += (p[k].A - H), H = p[k].A;
        H -= p[k].A;
        H += p[k].B;
    } // 先处理的
    for (int k : p2) {
        if (H < p[k].A)
            ans += (p[k].A - H), H = p[k].A;
        H -= p[k].A;
        H += p[k].B;
    } // 后处理的
    cout << ans;
    return 0;
}

闲话

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

大体思路与贪心证明

战争游戏

类似这题，我们最优情况需要把能力筹集完之后再清剿。我们看看哪些怪物能帮助我们最大增加能量呢？肯定是 $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;
}

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

总结

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