题目分析

问题描述

ACM公司需要在一栋大楼的走廊两侧搬运桌子：

1. 走廊两侧各有200个房间（共400个房间位置）
2. 每次搬运占用起点到终点之间的走廊区域
3. 同时进行的搬运不能共享任何走廊段
4. 每次搬运耗时10分钟
5. 目标：计算完成所有搬运的最短总时间

输入输出

• 输入：$T$个测试用例，每个包含$N$次搬运的起止房间号
• 输出：完成所有搬运的最少分钟数

---

解题思路

1. 关键观察

将走廊建模为线段区间：

• 每个搬运对应一个区间$[s,t]$
• 重叠的区间不能同时进行
• 所需时间由最大重叠次数决定

数学表达：

$$\text{总时间} = 10 \times \max_{x \in \text{走廊}} \{ \text{覆盖}x\text{的区间数} \} $$

2. 算法步骤

1. 区间处理：

• 将房间号映射为连续的走廊位置（奇偶处理）
• 对每个搬运$[s,t]$，统一调整为$[s',t']$格式

2. 统计覆盖次数：

• 初始化覆盖数组$d[405]$
• 对每个区间$[s,t]$，将$d[s..t]$加1

3. 计算最大重叠：

$$\text{max\_overlap} = \max_{i=1}^{400} d[i]$$ $$\text{总时间} = 10 \times \text{max\_overlap}$$

---

数学证明

1. 区间转换：

• 将房间号$r$映射为走廊位置：$$\text{pos}(r) = \begin{cases} r \times 2 - 1 & \text{if } r \text{在北侧} \\ r \times 2 & \text{if } r \text{在南侧} \end{cases} $$

2. 时间计算正确性：

• 最大重叠次数$k$表示至少需要$k$个时间段
• 每个时间段10分钟，故总时间为$10k$

---

复杂度分析

• 时间复杂度：$O(T \times N \times L)$
  • $L$=400（走廊长度）
  • 对每个测试用例：$O(NL)$
• 空间复杂度：$O(L)$

---

代码实现

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <stdlib.h>
#include <set>
//#define DEBUG
using namespace std;
typedef long long ll;
int T;
int n;
int s,t;
int d[405];
int main() {
    cin >> T;
        while(T--) {
            cin >> n;
            memset(d,0, sizeof(d));
            while(n--) {
                cin >> s >> t;
                if(s > t) swap(s,t);
                if(s % 2 == 0) s--;
                if(t % 2 == 1) t++;
                for(int i = s;i <= t;i++) {
                    d[i]++;
                }
            }
            sort(d,d+401,greater<int>());
            cout << d[0] * 10 << endl;
        }
 
    
    return 0;
}