浦东新区竞赛

竞赛链接：2026年浦东新区人工智能创新应用竞赛 如打不开，本文最后有原题截图。 题目分析 本题要求的是工程师的最小移动距离，并且其移动路径应满足： 起始点可以任选； 先检修低阶段的设备，再检修高阶段的设备。 同时，要检修一个设备$i$，工程师的位置必须处在$[segments[i][1], segments[i][2]]$范围内。 基本思路 由于检修设备的阶段应当保持非递减顺序，因此应当按照阶段对所有设备进行分组，并先将低阶段的组内所有设备检修完毕后，才去检修高阶段设备。 检修单个阶段内所有设备 现在先考虑对于一个阶段内的所有设备，如何才能够使将其检修完所移动的距离最小化。这时候就需要将所有可能性划分成两种情况： 这些设备所覆盖的区间均有交集，这时，如果工程师站在这个交集内，他即便是完全不移动，也可以检修完这个区间内的所有设备。并且可以发现：这个交集区间的左端点是所有区间左端点的最大值，右端点则是所有区间右端点的最小值。具体如下图： 这些设备所覆盖的区间并没有交集，这时，工程师无论如何都需要移动，但他移动的最小距离是什么呢？可以发现，如果同样求出来所有区间左端点的最大值$L_{max}$和右端点的最小值$R_{min}$(这时一定是$R_{min} < L_{max}$)，那么工程师向左只需要移动到$R_{min}$的位置即可检修左侧需要走最远的设备，同时向右只需要移动到$L_{max}$的位置即可检修右侧需要走最远的设备，因此在这种情况下，工程师至少要走过区间$[R_{min}, L_{max}]$中的所有点，才能处理完所有设备。具体如下图： 综上所述，无论如何都要求出来一个阶段内的左端点最大值和右端点最小值，才能知道处理完这个阶段的所有设备最少需要移动的距离，以及这个移动距离适用的起点范围。 整合多个阶段并计算最小移动距离 有了检修单个阶段内所有设备的最小移动距离，接下来要求的就是将每个阶段连接起来所需要的最小移动距离。按照阶段从小到大处理，对于第$i$大的阶段，如果能够知道从第$i-1$大的阶段转移到当前阶段所需要的最小移动距离，那么问题就转换成了处理第$i-1$大的阶段及之前所有阶段所需要的最小移动距离，这么看来，可以用动态规划来解决该问题。 定义动态规划数组$dp$，其中$dp[i]$表示检修完第$i$大阶段以及之前所有阶段中所有设备所需要的最小移动距离，并且$dp[i]$中存储着多个三元组$[cost, l, r]$，表示在完成这些任务后，工程师到达区间$[l,r]$中任意一个位置所需移动距离均为$cost$。 考虑转移方程，对于第$i$大阶段的处理，总共有以下两种情况： 该阶段内所有区间均有交集，且交集区间为$[L_{max}, R_{min}]$。这样，遍历$dp[i-1]$中的所有数据$[c_{i-1}, l_{i-1}, r_{i-1}]$，总共分三种情况进行讨论： $R_{min} < l_{i-1}$，也就意味着遍历到的这个上一个阶段对应的区间是在当前交集区间右侧的，而只要移动到这个交集区间内就可以不做任何移动处理完所有设备，因此可以从上一个阶段区间的左端点移动到当前交集区间的右端点，这样总共移动的距离就是$c_{i-1}+l_{i-1}-R_{min}$，同时这个距离只能适配一个位置$R_{min}$，故$dp[i]$中应当加上$[c_{i-1}+l_{i-1}-R_{min}, R_{min}, R_{min}]$； $r_{i-1} < L_{max}$，也就意味着上一个阶段遍历到的区间在当前交集区间左侧，与上面的情况同理，需要从上一个区间的右端点移动到当前交集区间的左端点才能使总移动距离最小，故总共移动距离就是 $c_{i-1}+L_{max}-r_{i-1}$，同样，这个距离也只对应一个位置$L_{max}$，故$dp[i]$中应加上$[c_{i-1}+L_{max}-r_{i-1}, L_{max}, L_{max}]$； 剩下情况一定意味着两个区间有交集，那么如果工程师能够处在这两个区间的交集中，他就不需要移动也可以处理完当前阶段内的所有设备，对应的，$dp[i]$中应当加上$[c_{i-1}, max(l_{i-1}, L_{max}), min(r_{i-1}, R_{min})]$。 该阶段所有区间并没有交集，即$R_{min} < L_{max}$，并且工程师至少要经过区间$[R_{min}, L_{max}]$内的所有位置，因此同样遍历$dp[i-1]$的所有数据$[c_{i-1}, l_{i-1}, r_{i-1}]$，分两种情况讨论，注意每种情况需要先遍历一遍求出最小距离后才加入$dp[i]$中： 如果要先到$R_{min}$，再到$L_{max}$，就要找到区间$[l_{i-1}, r_{i-1}]$中的所有位置到$R_{min}$的最短距离，加上$c_{i-1}$，再加上区间$[R_{min}, L_{max}]$的长度，即为当前情况下处理完第$i$大阶段的最小移动距离 （注意：这个距离适配的位置只有$L_{max}$，故加入$dp[i]$时三元组的区间应为$[L_{max},L_{max}]$）； 如果要先到$L_{max}$，再到$R_{min}$，就要找到区间$[l_{i-1}, r_{i-1}]$中的所有位置到$L_{max}$的最短距离，加上$c_{i-1}$，再加上区间$[R_{min}, L_{max}]$的长度，即为当前情况下处理完第$i$大阶段的最小移动距离 （注意：这个距离适配的位置只有$R_{min}$，故加入$dp[i]$时三元组的区间应为$[R_{min},R_{min}]$）。 最终返回最后一个$dp$列表中每个三元组中代价的最小值即可。 实现细节 需要注意的是，在动态规划转移方程的情况2的两个子情况中，需要求一个区间$[l,r]$中任意一点到达一个位置$x$的最短距离，可以用一个小函数来分情况计算： $x < l$，则返回$l-x$； $r < x$，则返回$x-r$； 否则，$x$在区间中，返回0. 复杂度 时间复杂度：$O(n\cdot logn)$ 空间复杂度：$O(n)$ ...