Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/problemset/problem/31/C 题意：给出n个借用教室的时间安排，可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。 思路：首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。
如果没有任何冲突，那么答案为n，直接输出一遍就好。
以l为第一关键字，r为第二关键字升序sort下。
如果有一个冲突，那么要看是否有包含关系，如果有，需要去掉大的这个，方案数为1.如果只是相交，那么可以去掉任意一个。方案数为2.
如果有两个冲突，我要看这两个冲突涉及到几个时间安排，如果涉及到4个或者时间安排，那么不可能全部解决，die掉。
如果这两个冲突涉及到三个时间安排，也就是说中间的和两段的相交，那么可以取消中间的这个时间安排来解决冲突。方案数为1.
需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月29日 星期二 21时37分11秒
4File Name :code/cf/problem/31C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define lson l,m,rt<<1
20#define rson m+1,r,rt<<1|1
21#define ms(a,x) memset(a,x,sizeof(a))
22typedef long long LL;
23#define pi pair < int ,int >
24#define MP make_pair
25
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=5E3+7;
32int n ;
33int ans[N];
34
35struct node
36{
37 int fst,sec;
38 int id;
39
40 bool operator <(node b)const
41 {
42 if (fst<b.fst) return true;
43 if (fst==b.fst&&sec<b.sec) return true;
44 return false;
45 }
46}a[N];
47int main()
48{
49 #ifndef ONLINE_JUDGE
50 freopen("code/in.txt","r",stdin);
51 #endif
52 cin>>n;
53 for ( int i = 1 ; i <= n ; i++) cin>>a[i].fst>>a[i].sec,a[i].id = i ;
54
55 sort(a+1,a+n+1);
56
57// for ( int i = 1 ; i <= n ; i++) cout<<a[i].fst<<endl;
58 a[n+1].fst = inf;
59 int num = 0 ;
60 bool ill=false,die=false;
61 for ( int i = 1 ; i <= n ; i++)
62 {
63 int j = i+1;
64 int cnt = 0;
65 while (a[j].fst<a[i].sec&&j<=n)
66 {
67 // cout<<"i:"<<i<<" j:"<<j<<endl;
68 if (ill)
69 {
70 die = true;
71 break;
72 }
73 j++;
74 cnt++;
75 }
76 if (die) break;
77
78 if (cnt==0) continue;
79 ill = true;
80 j--;
81
82 if (cnt>=2)
83 {
84 num++;
85 ans[num] = a[i].id;
86 }
87 else
88 {
89 if (a[j+1].fst<a[j].sec&&j+1<=n)
90 {
91 num++;
92 ans[num] = a[j].id;
93 i++;
94 }
95 else
96 {
97 num++;
98 ans[num] = a[i].id;
99 num++;
100 ans[num] = a[j].id;
101 }
102 }
103 }
104 if (die)
105 {
106 // cout<<"wwwww"<<endl;
107 puts("0");
108 return 0;
109 }
110 if (!ill)
111 {
112 cout<<n<<endl;
113 for ( int i = 1 ; i <= n-1 ; i++) printf("%d ",i);
114 printf("%d\n",n);
115 }
116 else
117 {
118 cout<<num<<endl;
119 sort(ans+1,ans+num+1); //id的顺序未必是升序。所以需要再次sort下。
120 for ( int i =1 ; i <= num-1 ; i++) printf("%d ",ans[i]);
121 printf("%d\n",ans[num]);
122 }
123
124 #ifndef ONLINE_JUDGE
125 fclose(stdin);
126 #endif
127 return 0;
128}