Posted on 2012-01-18 00:42
C小加 閱讀(1960)
評論(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];
//把左右界坐標真值儲存在結構體數(shù)組中
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];
//把左右界坐標真值儲存在結構體數(shù)組中
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;
}