P1607 [USACO09FEB] Fair Shuttle G
可以将所有组按照左端点排序。
如果当前的左端点大于等于某些在车上的牛，那他们就下车，答案增加。
然后，我们考虑插入这一组奶牛，我们发现同样是奶牛，我们肯定希望越早下车越好，这样可以为后面的牛腾出更多的空间，所以我们对于当前的这组牛，若放不下，我们试图删除当前下车时间最晚的一批牛（此时需要保证删除这批牛之后空间 \(\le\) 当前所需的空间），重复执行。
然后，我们遇到的局面有两类：
- 没有牛了，此时我们直接插入当前牛（注意不超过容量）。
- 还有牛，此时删除这批牛之后空间 \(>\) 当前所需的空间，那么我们只需要删除至恰好可以放下当前的这批牛（如果多删除，会导致错误。比如后面没有牛了）。
我们考虑用 set 维护，每次从小到大删除离开时间小于等于当前时刻的牛，从大到小删除更劣的牛。（其实有一个叫做双端堆的东西，之前想搞但是很难写）。
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=100010;
int n,c;
struct segment{
int l,r,t;
bool operator<(segment&A){
return l<A.l;
}
}seg[N];
struct cow{
int r,t;
bool operator<(const cow &A)const{
return r>A.r;
}
};
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d%*d%d",&n,&c);
E(i, n){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
seg[i]={a,b,c};
}
sort(seg+1,seg+1+n);
int ans=0,tot=0;
multiset<cow>s;
cow it;
E(i, n){
auto[l,r,t]=seg[i];
Wh(!s.empty()&&(it=*s.rbegin()).r<=l){
ans+=it.t;
tot-=it.t;
s.erase(prev(s.end()));
}
Wh(!s.empty()&&(it=*s.begin()).r>=r&&c-tot+it.t<=t){
s.erase(s.begin());
tot-=it.t;
}
if(!s.empty()&&(it=*s.begin()).r>=r&&c-tot+it.t>t&&c-tot<t){
s.erase(s.begin());
s.insert({it.r,it.t-(t-(c-tot))});
tot-=t-(c-tot);
}
s.insert({r,min(c-tot,t)});
tot+=min(c-tot,t);
}
Wh(!s.empty())ans+=(*s.begin()).t,s.erase(s.begin());
printf("%d",ans);
return 0;
}