Posted on 2012-05-06 14:50
C小加 閱讀(1502)
評論(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;
}