题意：

n个农场，有k群牛要从一个农场到另一个农场（每群由一只或几只奶牛组成）飞机白天从农场1到农场n，晚上从农场n到农场1，上面有c个座位，问最多可以满足多少只牛的要求。n≤10000，k≤50000，c≤100。

题解：

用类似贪心的方法做，现将每个农场出发的牛组织成链表。先求早上：当飞机到达每个农场时，先让到达的奶牛下机，接着如果飞机未满，则将其填满，之后枚举剩下的奶牛，如果它们的目的地比坐在飞机上面的奶牛目的地近，就将其替换为当前奶牛，这一过程可以用multiset维护。晚上所有过程都倒过来再做一次即可。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 10010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 multiset
         
          
            >st1;16 multiset
           
            st2;17 int n,m,k,now,ans; struct nd{ int t,w,n;}nds[2][maxn*5]; int ess[2],g[2][maxn];18 int main(){19 n=read(); m=read(); k=read();20 inc(i,1,n){21 int x=read(),y=read(),z=read();22 if(x
            
             nds[0][j].t&&nds[0][j].w)32 st1.erase(st1.begin()),st1.insert(nds[0][j].t),nds[0][j].w--;33 }34 }35 }36 now=0;37 for(int i=m;i>=1;i--){38 if(st2.find(i)!=st2.end()){ int x=st2.erase(i); ans+=x; now-=x;}39 for(int j=g[1][i];j;j=nds[1][j].n){40 while(now
            
           
          
         
        
       
      
     

 

20161115