学步园

标准的贪心算法

#include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> #define MAX 10002<br /> int a[MAX],b[MAX];//<br /> int cmp(const void *a,const void *b){<br /> return *(int*)a-*(int*)b;<br /> }<br /> void solve(){<br /> int m;int num=1,s=0;<br /> cin>>m;<br /> for(int i=0;i<m;++i){<br /> cin>>a[i]>>b[i];<br /> }<br /> qsort(a,m,sizeof(a[0]),cmp);<br /> qsort(b,m,sizeof(b[0]),cmp);<br /> for(int i=1;i<m;++i)<br /> if(a[i]>=b[s])s++;<br /> else num++;<br /> cout<<num<<endl;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> solve();<br /> return 0;<br /> }<br />