http://acm.hdu.edu.cn/showproblem.php?pid=1050
解题思路:这道题最少花多少时间,实际上我们只要考虑哪一段重合度最高,重合度最高的地方,也就是我们至少要移动的次数了。因为有400间房间,1-2对应一段走廊,3-4对应一段走廊,如此我们可以把走廊分成200段,标记为a[1]-a[200],之后我们根据输进的房间序号,就可以算出要用到哪几段的走廊,之后给对应的a[n]值加1就好,最后求出a[n]最大值就是移动的次数了。
int main()
{
int NumOfTest,pair;
int i,Max;
int a[201];
int b,c,n1,n2;
scanf("%d",&NumOfTest);
while (NumOfTest--)
{
scanf("%d",&pair);
memset(a,0,sizeof(a));
while (pair--)
{
scanf("%d%d",&b,&c);
if(b>c)/*交换数值,让小值在前,大值在后,从而使得n1<=n2*/
swap(b,c);
/*求n1和n2*/
if(b%2==1)
n1 = (b-1)/2+1;
else
n1 = b/2;
if(c%2==1)
n2 = (c-1)/2+1;
else
n2 = c/2;
if(n1!=n2)
for(i=n1;i<=n2;i++)
a[i]++;
else
a[n1]++;
}
Max = -1;
for(i=1;i<=200;i++)
if(Max<a[i])
Max = a[i];
printf("%d/n",10*Max);
}
return 0;
}