P2107 小Z的AK计划
Portal.
比较常规的反悔贪心。按照 x x x 从小到大选点，对于一个新到达的点，考虑它能否被选择。如果此时时间超过了 m m m，从前面的点按从大到小的顺序贪心地放弃 t i t_i ti 点，计算出选择这个点所能达到的全局点数。
注意要先假定这个点选，因为有可能放弃当前点，只是以当前位置为终止分界。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=1e5+5;
struct node{int x,t;}a[maxn];
priority_queue<int> q;bool cmp(node a,node b){return a.x<b.x;}signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].t;sort(a+1,a+n+1,cmp);int ans=0,tmp=0,cnt=0;for(int i=1;i<=n;i++){tmp+=a[i].x-a[i-1].x+a[i].t,q.push(a[i].t),cnt++;if(tmp>m) while(!q.empty()&&tmp>m) tmp-=q.top(),q.pop(),cnt--;if(tmp>m) break;ans=max(ans,cnt);}cout<<ans;return 0;
}