http://acm.hdu.edu.cn/showproblem.php?pid=1199
#include<stdio.h>
#include<stdlib.h>
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
struct H{
int start,end;
}hh[100001];
int k;
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int cmp(const void *a,const void *b)
{
struct H *c = (struct H *)a;
struct H *d = (struct H *)b;
return c->start - d->start;
}
void White()
{
int i;
qsort(hh,k,sizeof(hh[0]),cmp);
for(i=1;i<k;i++)
if(hh[i-1].start+1 && hh[i-1].end >= hh[i].start)
{
hh[i].start = hh[i-1].start;
if(hh[i-1].end>hh[i].end)
hh[i].end = hh[i-1].end;
}
}
void Black(int a,int b)
{
int i;
for(i=0;i<k;i++)
{
if(hh[i].start+1)
{
if(hh[i].start < a && b< hh[i].end)
{
hh[k].end=hh[i].end;
hh[k].start=b+1;
hh[i].end=a-1;
k++;
continue;
}
if(hh[i].start<=b && b<hh[i].end)
{
hh[i].start=b+1;
continue;
}
if(hh[i].start<a && a<= hh[i].end)
{
hh[i].end=a-1;
continue;
}
if(a<=hh[i].start && hh[i].end<=b)
{
hh[i].start=-1;
hh[i].end=-1;
continue;
}
}
}
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int main()
{
int T,a,b,max;
char com[2];
while(scanf("%d",&T)==1)
{
k = 0;
while(T--)
{
scanf("%d%d%s",&a,&b,com);
if(a>b)
a^=b^=a^=b;
if(com[0]=='w')
{
hh[k].start = a;
hh[k].end = b;
k ++;
}
else
{
Black(a,b);
}
}
White();
max = 0;
int j;
for(int i=0;i<k;i++)
{
if(hh[i].start!=-1)
{
int x = hh[i].end - hh[i].start + 1;
if(x>max)
{
max = x;
j = i;
}
}
}
if(max)
printf("%d %d\n",hh[j].start,hh[j].end);
else
puts("Oh, my god");
}
return 0;
}
這些是二維的：
http://acm.hdu.edu.cn/showproblem.php?pid=1543http://acm.hdu.edu.cn/showproblem.php?pid=1542http://acm.hdu.edu.cn/showproblem.php?pid=2704http://acm.hdu.edu.cn/showproblem.php?pid=1255
posted on 2009-03-28 18:54
shǎ崽 閱讀(565)
評論(0) 編輯 收藏 引用