其实做题可以先算法导向一下的。
比如看到显著特征：【最大值最小】，我们第一反应还是应该为二分答案转判定的。
考虑二分答案 \(d\)，此时转化为了，对于每个人 \(i\)，选择一个朝向左/右，向该朝向覆盖 \(d\) 的距离，能否将整个环全部覆盖。
如果不是环的话，很 lantern 啊！考虑序列情况，设 \(dp_i\) 表示考虑前 \(i\) 个人覆盖的最大前缀距离，对于转移：
- 若 \(dp_{i-1}\ge p_i-1\)，则第 \(i\) 个人可以向右覆盖，\(dp_{i}=p_i+d\)。
- 否则当前第 \(i\) 个人必须向左覆盖，此时若 \(dp_{i-2}\ge p_i-d-1\)，我们可以选择让 \(d_i\) 朝左，\(d_{i-1}\) 朝右，由于 \(d\) 相同，故当 \([d_{i-2},d_{i-1}]\) 被覆盖且 \(d_{i-1}\) 朝右时，\(d_{i-2}\) 再朝右是无意义的，所以我们只需要判到 \(dp_{i-2}\) 即可。此时 \(dp_i=p_{i-1}+d\)。否则若 \(dp_{i-1}\ge p_i-d-1\)，\(dp_i=p_i\)。
- 如果都不满足，则无解。最后若 \(dp_n\ge m\) 则有合法解。
考虑环会影响什么：会影响第 \(n\) 个人到第 \(1\) 个人之间边的覆盖情况。我们不妨尽可能地让这段特殊的环边再特殊再好处理一些，例如我们钦定这段环边为最大的一段环边，此时该环边长度一定大于 \(d\)（若答案为最大环边一定合法无需判定），我们就需要让该环边两侧都向该边有一个覆盖的距离。
考虑第 \(1\) 个人向哪里覆盖：
- 若向右覆盖，第 \(2\) 个人在最优情况下就必须向左覆盖，此时需满足 \(p_2\) 和 \(p_n\) 中间的空位置 \(\le 2d\)，则 \(dp_2=\max(d+1,a_2)\)，合法条件为 \(dp_n\ge \min(m,m+p_2-d-1)\)。
- 若向左覆盖，则 \(dp_1=1\)，合法条件为 \(dp_n\ge m-d\)。
故每次 check 跑两遍 dp 即可，时间复杂度 \(O(n\log n)\)。
对于环形问题，不妨先尝试弱化约束解决序列问题，扩展到环时尽可能将断掉的边特殊化。
标签：朝右,环边,覆盖,CF713E,ge,Sonya,个人,Partymaker,dp From： https://www.cnblogs.com/ydtz/p/17762708.html