[Naive] P12114 [NWRRC2024] Just Half is Enough

xiezheyuan · 2025-04-24 14:59:15 · 题解

很怀疑出题人的精神状态。首先注意到题目一共给出了给点排序的 m 条限制，而只需要满足 \lceil\frac{m}{2}\rceil 个要求即可。这说明如果我们构造出了一个不符合要求的方案，那么取其补方案（在本题中就是将排序反向，注意补方案会使得原本满足的限制不满足，反之亦然）就一定是符合要求的。所以只需要随便取一个排列判定是否合法，如果不合法就倒过来输出即可。时间复杂度 O(\sum n+m)，QOJ Submission。