题目链接:http://poj.org/problem?id=1083

如图所示在一条走廊的两侧各有200个房间,现在给定一些成对的房间相互交换桌子,但是走廊每次只能通过一组搬运,
也就是说如果两个搬运过程有交叉是不能同时搬运的,要依次来,一次搬运10min,问完成所有的搬运的最少用时。
 
思路:将每个左右相邻房间的走廊作为一个统计单位,当所有的办公桌都搬运完成后,检查每个走廊对应的统计单位被占用多少次。
统计所有的左右相邻房间的走廊被占用的最大次数,就是单独安排的搬运次数,乘以10就是总的搬运时间。
另外,将from和to做-1 mod 2 处理是为了与数组下标对应起来,方便处理
 #include <iostream>
#include <algorithm>
#include <functional>
#include <string.h>
#include <cstdio>
using namespace std; int main()
{
int t = ;
cin >> t;
while (t-- > )
{
// 每两个房间之间一个走廊,总共200个走廊
int move[];
int n = ; // 搬运次数
cin >> n;
memset(move, , sizeof(move));
for (int i = ; i < n; i++)
{
int from = , to = ;
cin >> from >> to;
from = (from - ) / ;
to = (to - ) / ;
if (to < from)
{
swap(from, to);
}
for (int j = from; j <= to; j++)
{
move[j]++;
}
}
int max = ;
for (int i = ; i < ; i++)
{
if (move[i] > max)
{
max = move[i];
}
}
cout << max * << "\n";
}
return ;
}
05-11 22:41