最长的白色段
题目描述
有一段从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
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <algorithm> using namespace std; int main() { int point[10001]; int bg[5001],ed[5001],b1,b2,e; int mx=0; char cr[5001]; int c[10000]; int n; int i,j,l; cin>>n; for(int i=1;i<=n;i++){ cin>>bg[i]>>ed[i]>>cr[i]; point[i]=bg[i]; point[n+i]=ed[i];} sort(point,point+2*n+1); for(i=1;i<2*n;i++) for(j=n;j>=0;j--) if(point[i]==bg[j]||(bg[j]<=point[i]&&ed[j]>point[i])||j==0) { if(cr[j]=='w'||j==0){c[i]=point[i+1]-point[i];break;} else {c[i]=-1;break;} } for(i=1;i<2*n;i++) { j=0,l=0; b1=point[i]; while(c[i+j]!=-1) { l+=c[i+j]; if(l>mx){mx=l;b2=b1;e=point[i+j+1];} j++; } } cout<<b2<<' '<<e; return 0; } |
计数器 9794881
OI 课件=>
OI 课件=>
这代码不像黄学长的风格呀……
orz