夏晓光(loveJY)的博客

考虑$O(n^2)$

我们就按照某种顺序排序,然后记录垫底深度为i的最多的人多少个就好

显然我们要先走那些矮的人,因为越高越好对人梯产生贡献

$f_{i,j}$表示前i个人走了j个,然后最大剩余高度是什么,这里翻转了信息

然后$O(nlogn)$

我们发现可以按照最低必需逃生高度排序,然后一定是先跑最低深度垫脚高的

就是$H-A-B$,不难发现这个是人梯所需的至少高度

然后我们考虑一个人,如果后面垫脚的和前面没跑的身高和已经满足了,那他一定可以跑掉,就先让他跑了

然后如果一个人不能跑掉,考虑能不能拉下之前的一个人

结论是如果之前那个人比他高,就一定可以拉下水,然后自己逃生,否则不行

这个结论可以考虑,因为之前那个人可以逃生,然后你会发现,那个人是垫着这个人上去的

然后交换顺序,这个人的逃生高度还比之前那个人要低,自然也肯定能

#include<bits/stdc++.h>
using namespace std;
#define pb push
const int MAXN = 1e5 + 7;
int n, H, ans;
struct rec {
	int A, B, p;
	bool operator<(const rec &x)const {
		return p > x.p;
	}
} a[MAXN];
int s[MAXN];
priority_queue<int> q;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d%d", &a[i].A, &a[i].B);
	scanf("%d", &H);
	for(int i = 1; i <= n; ++i)
		a[i].p = H - a[i].A - a[i].B;
	sort(a + 1, a + n + 1);
	for(int i = n; i >= 1; --i)s[i] = s[i + 1] + a[i + 1].A;
	int tot = 0;
	for(int i = 1; i <= n; ++i) {
		if(tot + s[i] >= a[i].p)ans++, q.pb(a[i].A);
		else {
			if(!q.empty() && q.top() > a[i].A) {
				tot += q.top();
				q.pop();
				q.pb(a[i].A);
			} else tot += a[i].A;
		}
	}
	printf("%d\n", ans);
	return 0;
}