尼玛。。我敢说这是我这辈子见过的最坑爹的题目了。。
这三个参数描述：从ai到bi,着颜色ci, ('w'表示白，'b'表示黑），可以认为0 < ai <= bi < 10**9
这句话完全不知道怎么理解，最开始认为ai到bi全部着色，下一个从bi+1开始判，然后交上去各种WA，看了discuss，说是[a,b)的区间，改了还是各种WA，无奈去找AC的程序，居然发现人家读的是（a，b]。。小菜实在无法理解其中的种种纠结，于是乎就仿照那个AC程序写了一个。。话说虽然AC了，程序的意思也明白，我还是不知道这个题到底是什么意思。。
我把程序的意思大体介绍下，就是读入a,b的时候，把place[a]+1到place[b]（离散，你们懂的）全部涂色，最后看连续的白色块比如1到3是白色的，那么就直接用3的坐标减去1的坐标得到解（假如3-4是白色的，但4端点被染黑，那么这段作废，不计入解（Orz求原因）），最后取最大解就OK。
下面上代码。。诚心希望有路过的牛帮忙解惑。。
#include<stdio.h>
typedef struct vtype
{
long a,b;
char z;
}vtype;
long now,i,n,pos,j,ans,jla,jlb,top,posa,posb,first,last;
vtype v[50000];
char f[50000];
long s[50000];
int find(int num)//二分查找num在数列中的位置
{
int l=1,r=pos,mid;
if (s[l]==num)
return l;
if (s[r]==num)
return r;
while (r-l>1)
{
mid=(l+r) >> 1;
(s[mid]<=num)? l=mid : r=mid;
if (s[l]==num) return l;
}
return l;
}
void sort(long l,long r)//快排不解释。。
{
long i,j,temp;
if (l>=r)
return;
i=l;j=r;temp=s[i];
while (i<j)
{
while (i<j && s[j]>temp)
j--;
if (i<j)
{
s[i]=s[j];
i++;
}
while (i<j && s[i]<temp)
i++;
if (i<j)
{
s[j]=s[i];
j--;
}
}
s[i]=temp;
sort(l,i-1);
sort(i+1,r);
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld %ld%c%c",&v[i].a,&v[i].b,&v[i].z,&v[i].z);
top++;s[top]=v[i].a;top++;s[top]=v[i].b;
}
top++;s[top]=0;top++;s[top]=1000000000;
sort(1,n*2+2);
s[0]=-1;
for (i=1;i<=n*2+2;i++)
if (s[i]!=s[i-1])
{
pos++;
s[pos]=s[i];
}
for (i=1;i<=pos;i++)
f[i]='w';
for (i=1;i<=n;i++)
{
posa=find(v[i].a)+1;
posb=find(v[i].b);//这就是我说的那种匪夷所思的取舍
for (j=posa;j<=posb;j++)
{
f[j]=v[i].z;
}
}
i=1;
s[0]=0;
while (i<=pos)//找最优解
if (f[i]=='w')
{
j=i;
while (f[j]=='w')
j++;
if (ans<s[j-1]-s[i-1])//这里i-1的原因。。自己debug调下就明白了。。
{
ans=s[j-1]-s[i-1];
jla=s[i-1];//记录一个端点坐标
jlb=s[j-1];//记录另一个端点坐标
}
i=j;
}
else
i++;
printf("%ld %ld",jla,jlb);
}
posted on 2011-06-28 21:45
梦转千寻 阅读(73)
评论(0) 编辑 收藏 引用