【题意】公车从1开到n，有k群牛想从一个点到达另一个点，公车最多乘坐c个人，牛群可以拆散，问最多载多少牛到达目的地。

【算法】贪心+堆

【题解】线段和点的贪心，一般有按左端点排序和按右端点排序两种方法。

按左端点排序，到达了终点就下车，人数满了就贪心地删掉当前终点最远的牛。

正确性在于，在对左一致的情况下，优先删除对右影响最大的牛。

本来以为很难实现，但是想清楚之后写起来十分顺畅，还是要有信心><

对于到达终点下车，按终点维护小根堆。

对于满人数贪心删终点最大的，维护大根堆。

用标号vis和剩余牛数num连接两个堆的删除。

复杂度O(k log k)。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=200010;struct cycmax{     int id,ed;     bool operator < (const cycmax &a)const{         return ed
         
          cmax;struct cycmin{    int id,ed;    bool operator < (const cycmin &a)const{        return ed>a.ed;    }};priority_queue
          
           cmin;struct cyc{    int l,r,num;}a[maxn];bool cmp(cyc a,cyc b){
    return a.l
           
            c){ cycmax x=cmax.top(); if(!vis[x.id]){ if(number-a[x.id].num>=c){ number-=a[x.id].num; vis[x.id]=1; 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 0;}
           
          
         
        
       
      

另一种做法，按右端点排序，能塞就塞，不能塞就不要，用线段树维护。（感性的理解一下，替换之前的效果一样却反而会占用到后面的，既然前面能解决的事为什么要交给后面的）