【题意】公车从1开到n，有k群牛想从一个点到达另一个点，公车最多乘坐c个人，牛群可以拆散，问最多载多少牛到达目的地。
【算法】贪心+堆
【题解】线段和点的贪心，一般有按左端点排序和按右端点排序两种方法。
按左端点排序，到达了终点就下车，人数满了就贪心地删掉当前终点最远的牛。
正确性在于，在对左一致的情况下，优先删除对右影响最大的牛。
本来以为很难实现，但是想清楚之后写起来十分顺畅，还是要有信心><
对于到达终点下车，按终点维护小根堆。
对于满人数贪心删终点最大的，维护大根堆。
用标号vis和剩余牛数num连接两个堆的删除。
复杂度O(k log k)。
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
struct cycmax{
int id,ed;
bool operator < (const cycmax &a)const{
return ed<a.ed;
}
};
priority_queue<cycmax>cmax;
struct cycmin{
int id,ed;
bool operator < (const cycmin &a)const{
return ed>a.ed;
}
};
priority_queue<cycmin>cmin;
struct cyc{
int l,r,num;
}a[maxn];
bool cmp(cyc a,cyc b){return a.l<b.l;}
int k,n,c,ans=,number=;
bool vis[maxn];
int main(){
scanf("%d%d%d",&n,&k,&c);
for(int i=;i<=n;i++){
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].num);
}
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++){
cmax.push((cycmax){i,a[i].r});
cmin.push((cycmin){i,a[i].r});
number+=a[i].num;
if(a[i].l!=a[i+].l){
while(!cmin.empty()&&cmin.top().ed<=a[i].l){
cycmin x=cmin.top();
if(!vis[x.id]){
ans+=a[x.id].num;
number-=a[x.id].num;
vis[x.id]=;
}
cmin.pop();
}
while(number>c){
cycmax x=cmax.top();
if(!vis[x.id]){
if(number-a[x.id].num>=c){
number-=a[x.id].num;
vis[x.id]=;
cmax.pop();
}
else{
a[x.id].num-=number-c;//zhu yi shun xu le!!!
number=c;
}
}else cmax.pop();
}
}
}
while(!cmax.empty()){
cycmax x=cmax.top();cmax.pop();
if(!vis[x.id])ans+=a[x.id].num;
}
printf("%d",ans);
return ;
}
另一种做法，按右端点排序，能塞就塞，不能塞就不要，用线段树维护。（感性的理解一下，替换之前的效果一样却反而会占用到后面的，既然前面能解决的事为什么要交给后面的）