Posted on 2012-05-06 14:50
C小加 阅读(1473)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
很遗憾比赛的时候没做出来，当时用贪心的方法写过，可是思路有问题，WA了。解题报告上面只说是贪心，但具体怎么写没有说。于是我就尝试了一些贪心想法，终于AC。24ms的时间还挺靠前的。
题意：N个老鼠洞和N个老鼠，老鼠有个兴趣区间[s,t]，就是说老鼠会对这个范围内的洞感兴趣，他们会占领自己感兴趣的洞。有一个兴趣波动范围K，求一个最小的K使得所有的老鼠都能占领自己感兴趣的洞。
分析：按照左边区间从小到大排序，然后开始枚举每一个区间，从区间右边的端点开始放，如果那个位置已经有老鼠的话，就向前遍历一遍看前边的洞是否已满，没有满的话就向前遍历，遇到左端点的值小于这个老鼠的左端点值时，就交换，直到遇到一个空洞。如果满了的话就向后遍历，遇到右端点大于这个老鼠的右端点时，就交换，直到遇到一个空洞。遍历的时候要时刻判断K的值，如果到达不了那个范围，就增大K的值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef
struct{
int s,t;
}ract;
ract r[503];
int line[503];
bool cmp(ract r1,ract r2)
{
if(r1.s==r2.s)
return r1.t<r2.t;
return r1.s<r2.s;
}
int main()
{
int t,pos=0;
scanf("%d",&t);
while(t--)
{
memset(line,-1,
sizeof(line));
int n;
scanf("%d",&n);
for(
int i=0;i<n;++i)
{
scanf("%d %d",&r[i].s,&r[i].t);
}
sort(r,r+n,cmp);
int k=0;
for(
int i=0;i<n;++i)
{
if(line[r[i].t]==-1)
//如果右端点的洞是空的
{
line[r[i].t]=i;
}
else {
int flag=0,temp=i;
if(r[i].t>1)
for(
int j=r[i].t-1;j>=1;--j)
//向前遍历，是否已住满
{
if(line[j]==-1) {flag=1;
break;}
}
if(flag==1)
for(
int j=r[i].t;j>=1;--j)
//如果没有住满就向前遍历
{
if(line[j]==-1)
//遇到空洞就住下
{
line[j]=temp;
if(r[temp].s>j)
k=max(k,r[temp].s-j);
//更新K值
break;
}
else if(r[line[j]].s<r[temp].s)
//如果当前洞中的老鼠的左端点小于移动的老鼠的左端点，就交换
{
int tmp2=line[j];
line[j]=temp;
if(r[temp].s>j)
k=max(k,r[temp].s-j);
temp=tmp2;
}
}
else {
for(
int j=r[i].t;j<=n;++j)
//如果已经住满就向后遍历
{
if(line[j]==-1)
{
line[j]=temp;
if(r[temp].t<j)
k=max(k,j-r[temp].t);
break;
}
else {
if(r[line[j]].t>r[temp].t)
{
int tmp2=line[j];
line[j]=temp;
if(r[temp].t<j)
k=max(k,j-r[temp].t);
temp=tmp2;
}
}
}
}
}
}
printf("Case #%d: %d\n",++pos,k);
}
return 0;
}