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
|
這個題目最直接的辦法是離散化,離散化了之后就好折騰了,因?yàn)椴僮髦噶詈苌?所以我選擇離散+樸素染色.
復(fù)雜度上界為O(M*M),這里M表示離散化后得到的區(qū)間個數(shù).
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 /* 區(qū)間由1開始數(shù),而不是由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 /* 刪除重復(fù)出現(xiàn)的數(shù)字 */
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 /* 對操作進(jìn)行離散處理 */
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
個別目標(biāo)遠(yuǎn)大的同學(xué)可能并不僅僅是想解決這個題目,這時候建議你使用離散化+線段樹,復(fù)雜度會大大地降低