学步园

在zoj论坛上随便翻贪心的题，发现这个了，CW昨天还说来着。

和活动安排是一样一样一样滴。。。只用看0点右边的就好了，内径和外径相当于起始时间和终止时间。

只不过这个是去掉最少的环数。

终于把sort怎么排序结构体弄会了，偶也~~

交了好多次，sort就是比qsort快！以后用sort吧~

就是那个头文件的那个单词不会背啊。。。算法的那个单词。。。algorithm~

#include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <string.h><br /> #include <algorithm><br /> using namespace std;<br /> struct circle<br /> {<br /> int begin,end;<br /> }circle[10001];<br /> typedef struct circle CIR;<br /> //qsort的比较函数<br /> int cmp( const void *a,const void *b)<br /> {<br /> return ((CIR*)a)->end - ((CIR*)b)->end;<br /> }<br /> //sort的比较函数<br /> bool cmp1(CIR a, CIR b)<br /> {<br /> return a.end < b.end;<br /> }<br /> /**************************************************************************/<br /> int n;<br /> int flag[10001];<br /> void Greedy() //贪心。。<br /> {<br /> memset(flag,0,sizeof(flag));<br /> int j=0;<br /> flag[j] = 1;<br /> for(int i=1; i<n; i++)<br /> if( circle[i].begin >= circle[j].end )<br /> {<br /> flag[i] = 1;<br /> j = i;<br /> }<br /> else<br /> flag[i] = 0;<br /> }<br /> int main(void)<br /> {<br /> while( cin >> n && n )<br /> {<br /> int sum = 0;<br /> for(int i=0; i<n; i++)<br /> cin >> circle[i].begin >> circle[i].end;<br /> // sort(circle,circle+n,cmp1);<br /> qsort( circle, n, sizeof(CIR),cmp);<br /> Greedy();<br /> for(int i=0; i<n; i++)<br /> if( flag[i] == 0 )<br /> sum ++;<br /> cout << sum << endl;<br /> }<br /> return 0;<br /> }<br />