POJ 1083移动桌子用时最少

本文主要是介绍POJ 1083移动桌子用时最少，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有400个房间，现在要搬一些物品，从room a到roomb 一次搬运需要时间是10分钟，且此次搬运期间room a和room b前的走廊是一直占用的，如果其他的搬运也要经过这些走廊，则它们不能同时进行，互不干扰的搬运可以同时进行。给出一组room a 到room b 问如何安排使搬运时间最小。

思路：运用结构体，然后排序，从小到大取最优解就可得到答案。但是这题我做了3个小时了，看起来简单，但是存在个陷阱。就是注意：2 to 3 和4 to 5 是不能同时进行的，而1 to 2和3 to 4是可以同时进行的，原因是门对着，所以不能同时搬运；1 to 4 和3 to 6 当然是不能同时进行的。还有就是取最优解的时候也是个不小的难点，用的是循环，直到出现最后的解才退出循环，这有点像回溯法一样。

代码如下：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct abc
{
int a,b;
}s[210];
bool cmp(abc x,abc y)
{
if(x.a==y.a) return x.b<y.b;
return x.a<y.a;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,i,j,sum=0,c[210];
cin>>n;
for(i=0;i<n;i++)
{
cin>>s[i].a>>s[i].b;
if(s[i].a>s[i].b) swap(s[i].a,s[i].b);
}
sort(s,s+n,cmp);
memset(c,0,sizeof(c));
while(1)
{
int p=-1;
for(i=0;i<n;i++)
{
if(c[i]==0)
{
if(p==-1)
{
p=i;
c[p]=1;
sum++;
}
else
{
if(s[i].a-s[p].b>1||(s[i].a-s[p].b==1&&s[i].a%2!=0))
{
c[i]=1;
p=i;
}
}
}
}
if(p==-1) break;
}
cout<<sum*10<<endl;
}
return 0;
}