POJ1083Moving Tables（简单模拟）

﹏ヽ暗。殇╰゛Y 2021-12-03 13:09 258阅读 0赞

题目链接：[http://poj.org/problem?id=1083][http_poj.org_problem_id_1083]

如图所示在一条走廊的两侧各有200个房间，现在给定一些成对的房间相互交换桌子，但是走廊每次只能通过一组搬运，

也就是说如果两个搬运过程有交叉是不能同时搬运的，要依次来，一次搬运10min，问完成所有的搬运的最少用时。

思路：将每个左右相邻房间的走廊作为一个统计单位，当所有的办公桌都搬运完成后，检查每个走廊对应的统计单位被占用多少次。

统计所有的左右相邻房间的走廊被占用的最大次数，就是单独安排的搬运次数，乘以10就是总的搬运时间。

另外，将from和to做-1 mod 2 处理是为了与数组下标对应起来，方便处理

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

[ ][http_poj.org_problem_id_1083]

转载于:https://www.cnblogs.com/ygsworld/p/11116548.html

[http_poj.org_problem_id_1083]: http://poj.org/problem?id=1083
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211203/5d21da87c88c4c18bb8977ccf37107f5.png