codeforces 31 C. Schedule
http://codeforces.com/problemset/problem/31/C 题意：给出n个借用教室的时间安排，可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。 思路：首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。
如果没有任何冲突，那么答案为n，直接输出一遍就好。
以l为第一关键字，r为第二关键字升序sort下。
如果有一个冲突，那么要看是否有包含关系，如果有，需要去掉大的这个，方案数为1.如果只是相交，那么可以去掉任意一个。方案数为2.
如果有两个冲突，我要看这两个冲突涉及到几个时间安排，如果涉及到4个或者时间安排，那么不可能全部解决，die掉。
如果这两个冲突涉及到三个时间安排，也就是说中间的和两段的相交，那么可以取消中间的这个时间安排来解决冲突。方案数为1.
需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。
/* ***********************************************
Author :111qqz
Created Time :2015年12月29日 星期二 21时37分11秒
File Name :code/cf/problem/31C.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define lson l,m,rt<<1
14#define rson m+1,r,rt<<1|1
15#define ms(a,x) memset(a,x,sizeof(a))
16typedef long long LL;
17#define pi pair < int ,int >
18#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=5E3+7;
7int n ;
8int ans[N];
1struct node
2{
3 int fst,sec;
4 int id;
1 bool operator <(node b)const
2 {
3 if (fst<b.fst) return true;
4 if (fst==b.fst&&sec<b.sec) return true;
5 return false;
6 }
7}a[N];
8int main()
9{
10 #ifndef ONLINE_JUDGE
11 freopen("code/in.txt","r",stdin);
12 #endif
13 cin>>n;
14 for ( int i = 1 ; i <= n ; i++) cin>>a[i].fst>>a[i].sec,a[i].id = i ;
sort(a+1,a+n+1);
1// for ( int i = 1 ; i <= n ; i++) cout<<a[i].fst<<endl;
2 a[n+1].fst = inf;
3 int num = 0 ;
4 bool ill=false,die=false;
5 for ( int i = 1 ; i <= n ; i++)
6 {
7 int j = i+1;
8 int cnt = 0;
9 while (a[j].fst<a[i].sec&&j<=n)
10 {
11 // cout<<"i:"<<i<<" j:"<<j<<endl;
12 if (ill)
13 {
14 die = true;
15 break;
16 }
17 j++;
18 cnt++;
19 }
20 if (die) break;
1 if (cnt==0) continue;
2 ill = true;
3 j--;
1 if (cnt>=2)
2 {
3 num++;
4 ans[num] = a[i].id;
5 }
6 else
7 {
8 if (a[j+1].fst<a[j].sec&&j+1<=n)
9 {
10 num++;
11 ans[num] = a[j].id;
12 i++;
13 }
14 else
15 {
16 num++;
17 ans[num] = a[i].id;
18 num++;
19 ans[num] = a[j].id;
20 }
21 }
22 }
23 if (die)
24 {
25 // cout<<"wwwww"<<endl;
26 puts("0");
27 return 0;
28 }
29 if (!ill)
30 {
31 cout<<n<<endl;
32 for ( int i = 1 ; i <= n-1 ; i++) printf("%d ",i);
33 printf("%d\n",n);
34 }
35 else
36 {
37 cout<<num<<endl;
38 sort(ans+1,ans+num+1); //id的顺序未必是升序。所以需要再次sort下。
39 for ( int i =1 ; i <= num-1 ; i++) printf("%d ",ans[i]);
40 printf("%d\n",ans[num]);
41 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}