百奇礼物

子任务1 用位掩码表示剩余人员集合。每个状态枚举发送者$a$及所有最近的接收者$b$，转移到移除两人后的状态，并记录选择以恢复操作顺序。时间复杂度为$O(2^N N^2)$，空间复杂度为$O(2^N+N^2)$。

最优值 设顺时针相邻人员之间的间隔为$D_1,\ldots,D_N$，其中$D_N=L-X_N+X_1$。奇数下标间隔和为，偶数下标间隔和为，答案是。

任意操作顺序都形成一个完美匹配。为每一对选取实际移动的最短圆弧，统计每个间隔被多少条圆弧覆盖。每个人恰好是一个圆弧的端点，所以其两侧间隔的覆盖次数奇偶性不同。因此，所有奇数间隔或所有偶数间隔都被奇数次覆盖，总距离至少为$\min(A,B)$。

选择两种交替相邻匹配中间隔和较小的一种。其总和至多$L/2$，所以每个被选间隔本身都是最短圆弧。还需按最近人员规则执行该匹配。

操作顺序 剩余人员之间，被选与未选间隔交替出现，设它们的和满足$A\le B$。若每一对从两个方向都不合法，则每个被选间隔都比两侧的未选间隔长。将所有不等式相加得到$2A>2B$，矛盾。因此至少有一对可从某个方向合法执行。

移除长度为$d$的一对后，相邻的两个未选间隔与该被选间隔合并，两类间隔和变为$A-d$与$B+d$。不等式保持成立，可以持续执行到最后。仅剩两人时，他们必然互为最近人员。

用双向链表维护当前圆上的左右邻居。每一步扫描剩余人员，若固定配对距离不大于发送者到左右邻居的距离，就执行该操作。圆上的最近人员必是左右邻居之一。时间复杂度为$O(N^2)$，空间复杂度为$O(N)$。

Solution written by GPT6.1