4023. 电梯请求 II
来源第 189 场双周赛 Q4难度困难分数2279
题目描述
给你一个整数 n 表示一栋建筑的楼层数,楼层编号从 0 到 n - 1 。
同时给你一个整数 start ,表示电梯的起始楼层,以及一个整数数组 requests ,其中 requests[i] 是电梯需要到达的楼层。requests 中的所有楼层都是 互不相同 的。
在时间 0 ,电梯在楼层 start ,所有请求都是 同时 发出的。
在所有请求被处理完之前的每一秒钟,电梯 恰好 移动一层,可以是 向上 也可以是 向下 。当电梯到达请求的楼层时,该请求会被 立即 处理。如果 start 出现在 requests 中,则该请求在时间 0 被处理。
对于每个未被处理的请求,每一秒钟你会受到 1 点惩罚。等价地说,在时间 t 处理一个请求,它对总惩罚的贡献是 t 。
返回处理所有请求所需的 最小 总惩罚。
示例 1:
输入: n = 6, start = 4, requests = [1,5]
输出: 6
解释:
- 从楼层 4(
start)移动到楼层 5 需要 1 秒。楼层 5 的惩罚是 1 。 - 从楼层 5 移动到楼层 1 需要 4 秒。楼层 1 的惩罚是 5 。
因此,总惩罚是 1 + 5 = 6 。
示例 2:
输入: n = 8, start = 3, requests = [3,7,1]
输出: 10
解释:
- 楼层 3(
start)会被立即处理。楼层 3 的惩罚是 0 。 - 从楼层 3 移动到楼层 1 需要 2 秒。楼层 1 的惩罚是 2 。
- 从楼层 1 移动到楼层 7 需要 6 秒。楼层 7 的惩罚是 8 。
因此,总惩罚是 0 + 2 + 8 = 10 。
示例 3:
输入: n = 10, start = 5, requests = [0,2,9]
输出: 22
解释:
- 从楼层 5(
start)移动到楼层 2 需要 3 秒。楼层 2 的惩罚是 3 。 - 从楼层 2 移动到楼层 0 需要 2 秒。楼层 0 的惩罚是 5 。
- 从楼层 0 移动到楼层 9 需要 9 秒。楼层 9 的惩罚是 14 。
因此,总惩罚是 3 + 5 + 14 = 22 。
提示:
1 <= n <= 1091 <= requests.length <= 15000 <= start, requests[i] <= n - 1requests中的所有值都是 互不相同 的。
解法
方法一
思考
楼层编号达 \(10^9\),但请求只有 \(m\le 1500\) 个且互异,路径只需在这些楼层之间规划。电梯每秒必须移动一层,惩罚是各请求被访问时刻之和,访问次序决定全部完成时间。
\(m\) 已超出状压 TSP 的范围,然而点在数轴上,最优路线由若干段单向扫过构成。
将请求按楼层排序后,可用 \(O(m^2)\) 的区间 DP 枚举下一段扫过的范围,避免在 \(10^9\) 层上建图。
1 | |
1 | |
1 | |
1 | |