Luogu P4823 [TJOI2013]拯救小矮人

题目

\(n^2\)的dp已经成为辣鸡做法了，%%%wch。

首先一个结论：\(a+b\)小的人在上。

这个东西我们有三种方法解决证明：

1、感性理解，\(a+b\)越大的人逃生能力越强，放在下面就越可能溜。

2、交换法。

3、找别的博客。

所以我们排个序确定顺序，然后来考虑如何计算最多能跑多少人。

然后我们记录高度的后缀和\(s_i\)，从上到下到第\(i\)个人时前面出不去的人的高度\(t\)。

如果第\(i\)个人能直接出去即\(t+s_i+b_i\)，那么让他直接溜。

如果出不去，并且把溜出去了的最高的人拉下来能够让他出去，并且溜出去了的最高的人比这个人高，我们就把溜出去了的最高的人拉下来，让这个人出去。

否则这个人就走不了了。

对于第二个操作，开个堆维护就好了。

考虑第二个操作的正确性：这个操作不会影响当前出去的人数，并且垫底的高度\(t\)一定会增加，后面的人就一定更容易出去。

而所有拉更多人下来的举动都可以归纳到拉一个人下来中。

#include<bits/stdc++.h>

using namespace std;

const int N=2007;

int s[N];

priority_queue<int>q;

struct node{int a,b;}p[N];

int operator<(node a,node b){return a.a+a.b<b.a+b.b;}

int read(){int x;scanf("%d",&x);return x;}

int main()

{

    int n=read(),i,h,t=0,ans=0;

    for(i=1;i<=n;++i) p[i].a=read(),p[i].b=read();

    sort(p+1,p+n+1),h=read();

    for(i=n;i;--i) s[i]=s[i+1]+p[i].a;

    for(i=1;i<=n;++i)

	if(s[i]+p[i].b+t>=h) q.push(p[i].a),++ans;

	else if(!q.empty()&&p[i].a<q.top()&&q.top()+s[i]+p[i].b+t>=h) t+=q.top(),q.pop(),q.push(p[i].a);

	else t+=p[i].a;

    return !printf("%d",ans);

}