http://acm.hdu.edu.cn/showproblem.php?pid=1050 题目的地址。
用贪心做的,但是看了DISCUSS发现有很神的办法。
为什么贴上来这道呢。主要是练习赛的时候发现交不了,然后换到主页就A掉了。
RP太差啊。
总体上思路很简单,有点像COJ的今年暑假不AC。
贴代码
#include <iostream>#include <cstdio>
#include <algorithm>
using namespace std;
struct kdq
{
int start,end;//起始和结束房间号对应的走廊距离
bool visit;//判断是否已经计算
}time[505];
bool cmp(kdq a,kdq b)
{
return a.start<b.start;
}
int main()
{
int i,j,k,l,n,m;
int T;
cin>>T;
int a,b;
while(T--)
{
cin>>n;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
a=(a+1)/2,b=(b+1)/2;//房间号对应的走廊距离
time[i].start=a<b?a:b;
time[i].end=a>b?a:b;
time[i].visit=0;
}
sort(time,time+n,cmp);//按start从小到大排序
int start=time[0].end;
time[0].visit=1;
int num=0;
while(1)//贪心
{
num++;
bool flag=0;
for(i=0;i<n;i++)
{
if(!time[i].visit)
{
if(time[i].start>start)
{
time[i].visit=1;
start=time[i].end;
}
}
}
for(i=0;i<n;i++)
{
if(!time[i].visit)
{
flag=1;
start=time[i].end;
time[i].visit=1;
break;
}
}
if(!flag)
break;
}
cout<<num*10<<endl;
}
return 0;
}
posted on 2012-06-30 22:55
invincible 阅读(265)
评论(0) 编辑 收藏 引用