题目链接：http://codeforces.com/problemset/problem/31/C
题目意思：给出 n 个 lessons 你，每个lesson 有对应的 起始和结束时间。问通过删除一个lesson后能否使得所有lesson 持续的时间互不相交。注意，如果某个lesson结束的时刻恰好是另一个 lesson 的开始时刻，那么这两个lesson 也看作是不相交的。
看了题目之后，一如既往地，没什么想法= =。C题好多时候都这样，继续努力！！！
想着看Tutorial 直接学习，怎么知道没有滴，可能是太过久远了。只能看别人代码学了，学了个用时最少的GNU C++，不由得感叹，该人的解决方法真是巧妙，给个赞他，太聪明了！！！
我们先假定每个lesson 占据的时间是一段段的，左右两个端点分别是起始和终止时刻。用一个统计每个时刻出现次数的数组temp，对于第 i 个lesson 起始时刻in[i][0] 就 temp[in[i][0]]++，终止时刻 in[i][1] 就temp[in[i][1]]-- 。这样构造的好处应该就是把所有lesson 统一于只有一条特长线段来处理，可以发现，如果某一个时刻出现3次以上，就无论删除哪个lesson 都不可能使得所有lesson 的时间都不相交了，恰好2次的话可以尝试删除其中一个lesson 来验证之。如果某个lesson的结束时刻ti 是另一个lesson的开始时刻，就标记这个 ti 为0次。
可以发现，如果有解的话，次数标记数组temp 不会有超过3个1的时刻或者某个时刻出现3次以上出现的。
有点只可意会不能言转啊，就是很佩服这个人的解题思路。应该是多年做题的经验和直觉啦。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 5000 + 5; 9 const int N = 1e6 + 2; 10 11 int in[maxn][2]; 12 int temp[N]; 13 vector<int> ans; 14 15 int main() 16 { 17 int n, i; 18 while (scanf("%d", &n) != EOF) 19 { 20 ans.clear(); 21 memset(in, 0, sizeof(in)); 22 memset(temp, 0, sizeof(temp)); 23 for (i = 1; i <= n; i++) 24 { 25 scanf("%d%d", &in[i][0], &in[i][1]); 26 temp[in[i][0]]++; 27 temp[in[i][1]]--; 28 } 29 int a = -1, b = -1; 30 int maxx = 0; 31 for (i = 1; i <= N; i++) 32 { 33 maxx += temp[i]; 34 if (maxx > 1) // <= 1表示本来的lesson已经两两不相交了，最终删除哪个lesson都满足条件 35 { 36 if (maxx >= 3) // 怎么删除都不符合条件,因为有多于两个以上的 lesson 占据这个时刻 37 { 38 printf("0 "); 39 return 0; 40 } 41 if (a == -1) 42 a = i; 43 b = i; 44 } 45 } 46 for (i = 1; i <= n; i++) 47 { 48 if (a == -1 || in[i][0] <= a && b <= in[i][1]-1) // [a,b] 表示最小可删除区间，大于等于这个区间的lesson都可以删除 49 ans.push_back(i); 50 } 51 printf("%d ", ans.size()); 52 if (ans.size()) 53 { 54 printf("%d", ans[0]); 55 for (int i = 1; i < ans.size(); i++) 56 printf(" %d", ans[i]); 57 printf(" "); 58 } 59 } 60 return 0; 61 }