带后悔的贪心

首先，我们设一场电影的持续时间时间为,结束时间为

假设，我们决定好了要看哪些电影

且其中一种合法的看电影顺序为

那么，我们来贪心的化下式子：

假设，我们调换了看第i部和第i+1部电影的顺序后，使得当前的顺序不合法了，(前i-1部用的总时长为S)那么有：

当前方案：

因为调换后不合法，那么有：

可以推出:

也就是说，如果我们明确了要看哪些电影，一定存在一种合法方案，使得观看顺序为按由小到大的顺序看

那么，我们就可以先按由小到大排个序，再依次观看电影即可。

那么，现在就是一个简单的带后悔的贪心问题了，直接用个堆维护当前已选电影的最大持续时间即可。（因为有贪心策略：当前时间早的可以看的电影数量，一定不会小于当前时间晚的（Ps:这个可以用决策包容性证明））

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=15e4+1;
struct node{
    int lon,ed;
}t[N];
inline bool kkk(node x,node y){
    return x.ed<y.ed;
}
priority_queue<int>s;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&t[i].lon,&t[i].ed);
    }
    sort(t+1,t+n+1,kkk);
    int now=0,ans=0;
    for(int i=1;i<=n;++i){
        if(now<=t[i].ed-t[i].lon){
            ++ans;now+=t[i].lon;
            s.push(t[i].lon);
        }else{
            if(t[i].lon<s.top()){
                now-=s.top();s.pop();now+=t[i].lon;
                s.push(t[i].lon);
            }
        }
    }
    printf("%d",ans);
    return 0;
}