涂色

Description

有一根长度为1000000000的棍子，一开始涂成白色。
棍子上有刻度，左端点为0，右端点1000000000。
由于某种原因这根棍子的某些部分被重新涂过了。
重新涂的颜色可能是黑色或着白色。
棍子总共被依次重新涂了N(1<=N<=5000)次。
找出最后最长的白色段。

Input

第1行一个数N。
接下来N行表示一次涂色，格式如下：
ai bi ci
ai和bi为整数,ci是字母b或w。
表示把ai和bi之间那段涂成ci色(w白***黑色)。

0<=ai<=bi<=1000000000。

Output

一行，两个数x和y(x如果有多个最长的段，输出x最小的一个。

Sample Input

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

Sample Output

47 634

题目分析

有两种颜色，求经过一系列操作后最长的白色段

解题思路

对于一段区域，我们要以涂色时间从后往前地去判断它是否存在且为白***r> 注意要记录位置

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
string z[5005];
int n,o,w,s,s1,s2,a[10005],x[5005],y[5005];
int main()
{
   
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
   
		scanf("%d%d",&x[i],&y[i]);
		cin>>z[i];
		a[2*i-1]=x[i];//离散化
		a[2*i]=y[i];
	}
	sort(a+1,a+2*n+1);
	w=1;
	for(int i=2;i<=2*n;i++)
	{
   
		int ok=0;
		for(int j=n;j>=1;j--)
		 if(a[i]<=y[j]&&a[i-1]>=x[j]&&z[j]=="w")//白色
		 {
   
			ok=1;
			o+=a[i]-a[i-1];
			break;
		 } 
		 else if(a[i]<=y[j]&&a[i-1]>=x[j]&&z[j]=="b")break;//黑色
		if(ok==1)
		 if(o>s)//判断大小
		 {
   
			s=o;//更新
			s1=w;
			s2=i;
		 } 
		if(ok==0)
		{
   
			w=i;
			o=0;
		}
	}
	cout<<a[s1]<<' '<<a[s2];
	return 0;
}

谢谢