[USACO 2009 Feb G]Fair Shuttle

Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.
FJ couldn't afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the $M_i$ (1 <= $M_i$ <= N) cows in group i wanting to ride from one stop $S_i$ (1 <= $S_i$ < $E_i$ ) to another stop $E_i$ ( $S_i$ < $E_i$ <= N) farther along the route.
The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.
Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

#include<bits/stdc++.h> struct act { int s,t,num; friend bool operator <(act a,act b) { if(a.t!=b.t) return a.t<b.t; return a.s<b.s; } }a[50010]; int end[111]; bool cmp(int x,int y) { return x>y; } int main() { int k,n,c; scanf("%d%d%d",&k,&n,&c); for(int i=1;i<=k;++i) scanf("%d%d%d",&a[i].s,&a[i].t,&a[i].num); std::sort(a+1,a+1+k); int sum=0; for(int i=1;i<=k;++i) { std::sort(end+1,end+1+c,cmp); for(int j=1;a[i].num&&j<=c;++j) if(end[j]<=a[i].s) { ++sum; end[j]=a[i].t; a[i].num--; } } printf("%d\n",sum); return 0; }

详情