Description

有一根長度為1000000000的棍子，一開始涂成白色。
棍子上有刻度，左端點為0，右端點1000000000。
由于某種原因這根棍子的某些部分被重新涂過了。
重新涂的顏色可能是黑色或著白色。
棍子總共被依次重新涂了N(1<=N<=5000)次。
找出最后最長的白色段。

Input

第1行一個數(shù)N。
接下來N行表示一次涂色，格式如下：
ai bi ci
ai和bi為整數(shù),ci是字母b或w。
表示把ai和bi之間那段涂成ci色(w白色,b黑色)。

0<=ai<=bi<=1000000000。

Output

一行，兩個數(shù)x和y(x如果有多個最長的段，輸出x最小的一個。

Sample Input

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

Sample Output

47 634
.
.
.
.
.
分析
離散化
對于一段區(qū)域，我們要以涂色時間從后往前地去判斷它是否存在且為白色
注意要記錄位置
.
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; long long x1[5001],y1[5001],x[10001]; char c[6000];int main() {scanf("%d",&n);for (int i=1;i<=n;i++){cin>>x1[i]>>y1[i]>>c[i];x[i*2-1]=x1[i];x[i*2]=y1[i];}sort(x+1,x+2*n+1);long long ans=0,fa1=0,wzx=1,ax=0,ay=0;for (int i=2;i<=2*n;i++){int bz=0;for (int j=n;j>=1;j--)if (x[i]<=y1[j]&&x[i-1]>=x1[j]&&c[j]=='w'){bz=1;fa1+=x[i]-x[i-1];break;} elseif (x[i]<=y1[j]&&x[i-1]>=x1[j]&&c[j]=='b') break;if (bz==1){if (fa1>ans){ans=fa1;ay=i;ax=wzx;}}if (bz==0){wzx=i;fa1=0;}}cout<<x[ax]<<' '<<x[ay];return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10292807.html

總結

以上是生活随笔為你收集整理的涂色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。