CSP-J模拟赛 T2 宴会 题解

yzm6677 · 2023-04-11 21:53:55 · 题解

update：这题我降橙了，难在思维上。

首先，可以证明宴会举行的点不在数轴的点上就在两点的正中间。那么立刻就能得到一种暴力解法：对每个这样的点进行枚举，每次做计算，挑最小值作为答案。但很明显这样非常慢。

接着，我们想到二分方法：将位置 x_0 二分，发现此时 x_0 不一定具备决策单调性。于是再考虑二分宴会开始时间 T，然后计算每人的活动区间范围（改变位置）：

• 如果 T < t_i，则只能取更大值。
• 否则第 i 个人的活动区间为 [x_i-(T-t_i),x_i+(T-t_i)]。

最后所有区间取交集后判断是否合法（即左端点小于右端点），符合则 T 可以更小，否则只能更大。二分求出开始时间 T 后，因为答案唯一，所以对所有人再作上述操作确定区间，最后一定得到一个唯一解。

但这样时间复杂度也是 O(n^2 \log n)，需要进一步优化。下面讲正解。

注意到如果不考虑换装时间，那么使用贪心算法，打擂台找最大和最小，取中间值。

那么我们只考虑两边点的准备时间，我们可以证明哪边的点准备时间多 1 秒，位置就往那里移动 0.5 个单位长度。那么就很好解决了，统计两头的准备时间在相应调整即可。

注意：多测不清空，爆零两行泪！！