A Line painting
Time Limit: 2.0 second
Memory Limit: 16 MB
The segment of numerical axis from 0 to 109
is painted into white color. After that some parts of this segment are
painted into black, then some into white again and so on. In total
there have been made N re-paintings (1 ≤ N ≤ 5000). You are to write a program that finds the longest white open interval after this sequence of re-paintings.
Input
The first line of input contains the only number N. Next N lines contain information about re-paintings. Each of these lines has a form:
ai bi ci
where ai and bi are integers, ci is symbol 'b' or 'w', ai, bi, ci are separated by spaces.
This triple of parameters represents repainting of segment from ai to bi into color ci ('w' — white, 'b' — black). You may assume that 0 < ai < bi < 109.
Output
Output should contain two numbers x and y (x < y)
divided by space(s). These numbers should define the longest white open
interval. If there are more than one such an interval output should
contain the one with the smallest x.
Sample
| input |
output |
4
1 999999997 b
40 300 w
300 634 w
43 47 b
|
47 634
|
这个题目最直接的办法是离散化,离散化了之后就好折腾了,因为操作指令很少,所以我选择离散+朴素染色.
复杂度上界为O(M*M),这里M表示离散化后得到的区间个数.
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int MAXN=10005;
5 const int MAXL=1000000000;
6 struct re
7 {
8 int a,b;
9 char c;
10 }op[MAXN];
11
12 int n,p=0,que[MAXN];
13 bool color[MAXN<<1];
14
15 /* 二分查找 */
16 int find(int num)
17 {
18 int l=0,r=p+1,mid;
19 while (r-l>1)
20 {
21 mid=(l+r) >> 1;
22 (que[mid]<=num)? l=mid : r=mid;
23 if (que[l]==num) return l;
24 }
25 return l;
26 }
27
28 void disp(re& op)
29 {
30 /* 区间由1开始数,而不是由0开始 */
31 op.a=find(op.a)+1;
32 op.b=find(op.b);
33 }
34
35 void mark(int l,int r,char c)
36 {
37 for (int i=l;i<=r;++i) color[i]=(c=='b');
38 }
39
40 int main()
41 {
42 // freopen("data.in","r",stdin);
43 // freopen("data.out","w",stdout);
44 cin >> n;
45 for (int i=0;i<n;++i)
46 {
47 cin >> op[i].a >> op[i].b >> op[i].c;
48 que[++p]=op[i].a;
49 que[++p]=op[i].b;
50 }
51 que[++p]=MAXL;
52 /* 删除重复出现的数字 */
53 int rp=0;
54 for (int i=1;i<=p;++i)
55 if (que[rp]!=que[i]) que[++rp]=que[i];
56 p=rp;
57 /* 排序,便于定位和离散化 */
58 sort(que,que+p+1);
59 que[p+1]=MAXL+1;
60 /* 对操作进行离散处理 */
61 for (int i=0;i<n;++i) disp(op[i]);
62 /* 处理操作序列 */
63 memset(color,0,sizeof(color));
64 for (int i=0;i<n;++i) mark(op[i].a,op[i].b,op[i].c);
65 int t=1,a,b,mlen=0;
66 for (int i=2;i<=p+1;++i)
67 if (color[i]!=color[t] || i>p)
68 {
69 if ((!color[t]) && (que[i-1]-que[t-1]>mlen)) { a=que[t-1];b=que[i-1];mlen=que[i-1]-que[t-1];}
70 t=i;
71 }
72 cout << a << ' ' << b << endl;
73 //system("pause");
74 return 0;
75 }
76
个别目标远大的同学可能并不仅仅是想解决这个题目,这时候建议你使用离散化+线段树,复杂度会大大地降低