Jennie

反悔贪心

显然要把逃生能力弱的先送出去，也就是排个序。

这时候剩下的怎么办，万一有一些手长腿短的怎么办

先假设所有小矮人站成一排，然后一个个逃。

逃无可逃时候，看看把已经逃出去的中腿最长的拉下来会不会答案更优。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int n;
struct dw{
    int a;
    int sum;
    friend bool operator <(dw x,dw y){
        return x.a<y.a;
    } 
}dd[100005];
priority_queue<dw> q;
bool cmp(dw x,dw y){
    return x.sum==y.sum?x.a>y.a:x.sum<y.sum;
}
int h;
int st;
int cnt;
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        read(dd[i].a);read(dd[i].sum);
        dd[i].sum+=dd[i].a;
        st+=dd[i].a;
    }
    read(h);
    sort(dd+1,dd+n+1,cmp);
    for(int i=1;i<=n;++i){
        //cout<<st<<endl;
        if(st+dd[i].sum-dd[i].a>=h){
            st-=dd[i].a;
            q.push(dd[i]);
            continue;   
        }
        if(!q.empty()){
            if(st+q.top().a+dd[i].sum-dd[i].a>=h){
                if(q.top().a>dd[i].a){
                    st+=q.top().a-dd[i].a;
                    q.pop();
                    q.push(dd[i]);
                    cnt++;
                    continue;
                }
            }
        }
        cnt++;
    }
    cout<<n-cnt;
    return 0;
}