【9018:1060】最长的白色段

1060: 最长的白色段

时间限制: 1 Sec 内存限制: 128 MB
提交: 340 解决: 93
[提交][状态][讨论版]

题目描述

有一段从0到1000000000的数轴，它开始的颜色是白色。现在有人不断把其中的一段染成黑色或白色，总共染了N段（1≤N≤5000）。你的任务是编写一个程序，找出最后最长的白色段。

输入

第一行只有一个数N，接下来的N行是每次染一段的信息，格式为：ai,bi,ci。
ai,bi是整数,ci是符号’b’或’w’，三者用空格隔开，表示这次从ai染到bi，用的颜色为ci（’b’表示黑色，’w’表示白色），你可以认为0<ai≤bi<1000000000。

输出

仅两个数x，y（x<y），用空格隔开，表示最长的白色段。如果有多个解，则输出x最小的解。

样例输入

4
1 999999997 b
40 300 w
300 634 w
43 47 b

样例输出

47 634

题解：n久以前的题，离散化+二分即可。

代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,a[10002],ans,ansx,ansy;
 6 bool col[10002];
 7 struct linet{int x,y;char c;}seq[5001];
 8 void init(){
 9     scanf("%d",&n);
10     col[2*n+1]=1;
11     for(int i=1;i<=n;i++){
12         scanf("%d %d %c",&seq[i].x,&seq[i].y,&seq[i].c);
13         a[2*i-1]=seq[i].x; a[2*i]=seq[i].y;
14     }
15     a[0]=0; a[2*n+1]=1000000000;
16     sort(a,a+2*n+2);
17 }
18 int bs(int l,int r,int key){
19     if(l>r) return 0;
20     int mid=(l+r)>>1;
21     if(a[mid]==key){
22         if(mid-1>=0&&a[mid-1]==key) return bs(l,mid-1,key);
23         else return mid;
24     }
25     if(a[mid]>key) return bs(l,mid-1,key);
26     else return bs(mid+1,r,key);
27 }
28 int main()
29 {
30     init();
31     for(int i=1;i<=n;i++){
32         int xx=bs(0,2*n+1,seq[i].x),yy=bs(0,2*n+1,seq[i].y);
33         for(int j=xx;j<yy;j++) col[j]=(seq[i].c=='w'?0:1);
34     }
35     for(int i=0;i<2*n+1;i++){
36         if(!col[i]){
37             int tmp=i;
38             while(i+1<=2*n+1&&!col[i+1]) i++;
39             if(a[i+1]-a[tmp]>ans){
40                 ans=a[i+1]-a[tmp];
41                 ansx=a[tmp]; ansy=a[i+1];
42             }
43         }
44     }
45     printf("%d %d
",ansx,ansy);
46     return 0;
47 }