模拟的第一道题，看到时的第一眼就觉得我肯定不会，虽然后来也知道怎么写，但是万恶的马拉松dbug真是令人脱发。。。
题目背景
快noip了，yyy很紧张！
题目描述
现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。
yyy认为，参加越多的比赛，noip就能考的越好（假的）
所以，他想知道他最多能参加几个比赛。
由于yyy是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。
输入输出格式
输入格式：第一行是一个整数n ，接下来n行每行是2个整数ai,bi(ai<bi)，表示比赛开始、结束的时间。
输出格式：一个整数最多参加的比赛数目。
输入输出样例
说明
对于20%的数据，n≤10；
对于50%的数据，n≤1000；
对于70%的数据，n≤100000；
对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。
首先，这道题的思路应该很明确：通过找特殊点来决定取舍。显然对于线段只有左右端点，由此我们可以简单推理一下：
如果我们要使得保留的线段越多，那么我们每选择保留一个线段时，就要使这个线段与其他线段相交的可能性越少。因此我们一定要保留右端点最小的线段（贪心），那么我们就要舍去与它相交的所有线段（即左端点坐标小于基准线段右端点坐标），那么我们再找第二小且不与原线段相交的线段，执行相同的操作，一直到没有任何两条线段相交。
既然说用到了贪心算法，那么我们就要验证无后效性（以后的状态不会影响到之前的状态），对于这道题来说：由于在对前一条线段进行处理后，这个线段就不会再与任何线段扯上关系，由此就验证了无后效性。
那么关于代码实现，我们可以先排一个序，将右端点最小的排在前面，再从第一条线段进行处理，删去与它相交的线段，再找第二小的且未被删除的线段，最后输出剩余线段数即可。
在这道题上我犯了一个小错误：用结构体储存线段取舍，舍去一条就在总数上减去，没有意识到之前减过的线段也会再被减一遍。。。
最后，附上本题代码
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int ans; 5 struct orz 6 { 7 long long ai,bi; 8 int bo; 9 } a[1000005]; 10 bool cmp(orz x, orz y) 11 { 12 return x.bi<y.bi; 13 } 14 void dfs(int k,int n) 15 { 16 for(int i=k+1;i<=n;i++) 17 { 18 if(a[i].ai<a[k].bi) 19 { 20 a[i].bo=1; 21 } 22 } 23 } 24 int main() 25 { 26 int n; 27 scanf("%d",&n); 28 for(int i=1; i<=n; i++) 29 { 30 scanf("%d%d",&a[i].ai,&a[i].bi); 31 } 32 sort(a+1,a+n+1,cmp); 33 for(int i=1; i<=n; i++) 34 { 35 if(a[i].bo==0) 36 { 37 ans++; 38 dfs(i,n); 39 } 40 } 41 printf("%d",ans); 42 return 0; 43 }