[USACO 2017 Feb S]Why Did the Cow Cross the Road

Farmer John's cows are trying to learn to cross the road effectively. Remembering the old "why did the chicken cross the road?" joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them.

As it turns out, chickens are very busy creatures and have limited time to help the cows. There are CC chickens on the farm (1≤C≤20,000), conveniently numbered 1…C, and each chicken i is only willing to help a cow at precisely time $T_i$ . The cows, never in a hurry, have more flexibility in their schedules. There are N cows on the farm (1≤N≤20,000), conveniently numbered 1…N, where cow j is able to cross the road between time $A_j$ and time $B_j$ . Figuring the "buddy system" is the best way to proceed, each cow j would ideally like to find a chicken i to help her cross the road; in order for their schedules to be compatible, i and j must satisfy .

If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed.

The first line of input contains C and N. The next CC lines contain

, and the next N lines contain $A_j$ and $B_j$ (

) for j=1…N. The A's, B's, and T's are all non-negative integers (not necessarily distinct) of size at most 1,000,000,000.

#include<bits/stdc++.h> using namespace std; int n,m,a[200005],flag[200005],ans; struct node{ int sta; int end; }b[200005]; int cmp(node x,node y) { return x.end<y.end; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) cin>>b[i].sta>>b[i].end; sort(a+1,a+1+n); sort(b+1,b+1+m,cmp); for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) { if(flag[i]==0&&a[i]>=b[j].sta&&a[i]<=b[j].end) { ans++; flag[i]=1; break; } } } cout<<ans<<endl; return 0; }

详情