Posted on 2012-01-18 00:42
C小加 阅读(1937)
评论(6) 编辑 收藏 引用 所属分类:
解题报告
离散化+朴素算法。当然用线段树也可以过，我主要是想练习一下离散化，所以直接朴素了（更新5000次以内，离散化后的长度1万以内）。谁会想到半夜这个时候我居然在切题。第二次写离散化，可能与第一次隔的时间有点长，写的一塌糊涂。大家眼中的水题被我搞得人不像人，鬼不像鬼。好失落。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline
int L(
int r){
return r<<1;}
inline
int R(
int r){
return ((r<<1)+1);}
const int MAXM=5003;
typedef
struct{
int zy,value;
}line;
line node[MAXM*2];
int post[MAXM][2];
char col[MAXM][2];
int l[MAXM*2];
int zz[MAXM*2];
void ranse(
int b,
int e,
int c)
{
for(
int i=b;i<e;i++)
{
l[i]=c;
}
}
bool cmp(line l1,line l2)
{
return l1.value<l2.value;
}
int main()
{
int n;
scanf("%d",&n);
post[0][0]=0;
post[0][1]=1000000000;
col[0][0]='w';
node[L(0)].zy=-0-1;
//左值为负
node[R(0)].zy=0+1;
//右值为正
node[L(0)].value=post[0][0];
//把左右界坐标真值储存在结构体数组中
node[R(0)].value=post[0][1];
for(
int i=1;i<=n;i++)
{
scanf("%d %d %s",&post[i][0],&post[i][1],col[i]);
//getchar();
node[L(i)].zy=-i-1;
//左值为负
node[R(i)].zy=i+1;
//右值为正
node[L(i)].value=post[i][0];
//把左右界坐标真值储存在结构体数组中
node[R(i)].value=post[i][1];
}
sort(node,node+(n+1)*2,cmp);
//对所有坐标进行排序
int count=0,temp=node[0].value;
//count为离散化后坐标值。
for(
int i=0;i<2*(n+1);i++)
{
if(node[i].value!=temp)
//如果坐标不同，则坐标加1
{
count++;
temp=node[i].value;
}
if(node[i].zy<0) post[-node[i].zy-1][0]=count;
//新post为离散化过后，左右界值
else post[node[i].zy-1][1]=count;
zz[count]=node[i].value;
}
memset(l,0,
sizeof(l));
l[count]=1;
for(
int i=0;i<=n;i++)
{
if(col[i][0]=='w') ranse(post[i][0],post[i][1],0);
else ranse(post[i][0],post[i][1],1);
}
int sum=0;
int ans=0;
int z,y,ansz,ansy;
for(
int i=0;i<=count;i++)
{
if(l[i]==0)
{
if(sum==0) z=zz[i];
sum++;
}
else {
if(sum!=0)
{
y=zz[i]-z;
if(y>ans)
{
ans=y;
ansz=z;
ansy=zz[i];
}
sum=0;
}
}
}
printf("%d %d\n",ansz,ansy);
return 0;
}