@[我不是sb我是bs](/user/482254)
二分答案 $t$，之后 $O(n)$ 验证能否在 $t$ 内干掉所有“椅子”
枚举每一个椅子段，如果这一段的长度 $l$ 满足 $t<l\le 2t$，那么就必须用两个人相向而行才能干掉；否则一个人就够。
事先将段按照长度排序，每次 check 优先固定长度大于 $t$ 的，之后看剩余的段能不能匀过来。
总时间复杂度 $O(n \log n)$
by Echidna @ 2022-05-14 16:31:21
如果是图上的情况，那最优的方法应该是点C、点E相向而行，点B、点D相反而行。
@[Echidna](/user/82284)
by zswangziye @ 2022-05-14 16:44:58
@[zswangziye](/user/243962) @[我不是sb我是bs](/user/482254)
确实没考虑到这种情况
二分答案 $t$ 。如果不存在一个椅子段长度大于 $t$ ，则这个答案一定可行，可以增大 $t$，否则 check。
于是在 check 时，一定有一段长度大于 $t$ 。考虑将这一段从中间裂开，破环为链。容易证明这样破环的正确性。
接着考虑破环为链之后的序列，可以使用贪心算法：假设现在前 $x$ 个椅子都已经被破掉了，找到一个最靠右的节点 $q$ 满足 $pos_q-t\le x$ ，让 $q$ 向左走，让 $q-1$ 向右走。
by Echidna @ 2022-05-14 17:22:06
@[Echidna](/user/82284) 不懂就问，$pos_q$是啥
by _AIR @ 2022-05-14 21:29:56
@[我不是sb我是bs](/user/482254) 就是破环为链之后 $q$ 的位置
我没说清楚 
by Echidna @ 2022-05-14 21:30:53
@[Echidna](/user/82284) 二分答案t如果满足不应该是减小吗
by _AIR @ 2022-05-14 21:33:54
@[我不是sb我是bs](/user/482254) 对 我打错了
by Echidna @ 2022-05-14 21:34:43
@[Echidna](/user/82284) 好的感谢
by _AIR @ 2022-05-14 21:35:59
@[我不是sb我是bs](/user/482254)
草 不一定对哦！
by Echidna @ 2022-05-14 21:37:24
@[我不是sb我是bs](/user/482254)
不知道这个题是怎么搞出来的，看样子是某个 OIer 出的题，然后不会 std 就来洛谷问
这个题我的贪心正确性不能保证，如果没有已知的 std 的话，这题有没有 std 都不能保证。
by Echidna @ 2022-05-14 21:38:51