-
题目描述
- 在一个狭窄的走廊里将桌子从一个房间移动到另一个房间，走廊的宽度只能允许一个桌子通过。给出 t，表示有 t 组测试数据，再给出 n，表示要移动 n 个桌子。n 下面有 n 行，每行两个数字，表示将桌子从 a 房间移动到 b 房间。走廊的分布图如图所示，每移动一个桌子到达目的地需要 10 分钟，问移动 n 个桌子需要的时间
- 图
-
输入
3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50 -
输出
10
20
30 -
问题分析
- 两次搬运过程不冲突，则可以同时搬运，所谓不冲突指的就是 某一次搬运过程中，所占用的区间范围在另外一次搬运过程之外，对于 [10,100] 区间，凡是在此区间内的区间都会与其发生冲突，而比如 [10,20] 和 [30,40] 就不会冲突
- 输入数据可能由大房间号移动至小房间号，事实上，都可以看成从小房间号移动到大房间号
- 出发房间为偶数房间则减一，结束房间为奇数则加一，使其始终满足从左上到右下，因为 2 到 6 和 1 到 6 是一样的，1 到 3 和 1 到 4 是一样的，每次移动给位置数组元素加十，如果在某位置上还有移动，则继续加，最后找出最大的数组元素就是结果
-
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int t,n,count[410],i,start,end;
cin>>t;
while(t--)
{
cin>>n;
memset(count,0,sizeof(count));
while(n--)
{
cin>>start>>end;
if(start>end)
swap(start,end);
if(start%2==0)
start-=1;
if(end%2==1)
end+=1;
for(i=start;i<=end;++i)
count[i]+=10;
}
cout<<*max_element(count,count+400);
}
return 0;
}