URAL 1019 A line painting
A Line painting
Time Limit: 2.0 second
Memory Limit: 16 MB
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.
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 |
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
個別目標遠大的同學可能并不僅僅是想解決這個題目,這時候建議你使用離散化+線段樹,復雜度會大大地降低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
posted on 2009-07-20 15:00 Chen Jiecao 閱讀(439) 評論(0) 編輯 收藏 引用 所屬分類: URAL