POJ1083Moving Tables（简单模拟）

佚名 5年前 (2019-07-01) 算法 1867人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。如图所示在一条走廊的两侧各有200个房间，现在给定一些成对的房间相互交换桌子，但是走廊每次只能通过一组搬运，也就是说如果两个搬运过程有交叉是不能同时搬运的，要依次来，一次搬运10min，问完成所有的搬运的最少用时。思路：将每个左右相邻房间的走廊作为一个统计单位，当所有的办公桌都搬运完成后，检查每个走廊对应的统计单位被占用多少次。统计所有的左右相邻房间的走廊被占用的最大次数，就是单独安排的搬运次数，乘以10就是总的搬运时间。另外，将from和to做-1 mod 2 处理是为了与数组下标对应起来，方便处理

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <functional>
 4 #include <string.h>
 5 #include <cstdio>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int t = 0;
11     cin >> t;
12     while (t-- > 0)
13     {
14         // 每两个房间之间一个走廊，总共200个走廊
15         int move[200];
16         int n = 0; // 搬运次数
17         cin >> n;
18         memset(move, 0, sizeof(move));
19         for (int i = 0; i < n; i++)
20         {
21             int from = 0, to = 0;
22             cin >> from >> to;
23             from = (from - 1) / 2;
24             to = (to - 1) / 2;
25             if (to < from)
26             {
27                 swap(from, to);
28             }
29             for (int j = from; j <= to; j++)
30             {
31                 move[j]++;
32             }
33         }
34         int max = 0;
35         for (int i = 0; i < 200; i++)
36         {
37             if (move[i] > max)
38             {
39                 max = move[i];
40             }
41         }
42         cout << max * 10 << "\n";
43     }
44     return 0;
45 }