P8088 『JROI-5』Autumn

· · 题解

官方题解。

C

算法一

根据传统套路，考虑二分答案，注意到如果 x 在某种交换策略下可以达到，那么最终的答案必然小于等于 x.

那么我们二分最终的答案，例如当前二分到的是 k_0，那么我们把集合中大于 k_0 的赋值为 1，其余为 0，\mathcal{O}\left(n\right)

判断即可，综合实践复杂度 \mathcal{O}\left(nm\log R\right) 其中 R 为 值域，结合前两个 Subtask，可以通过 70\% 的部分分。

算法二

不排除有松怪可以用上述做法松过这个 Subtask.

考虑把序列分成两个部分来维护，分别维护每个集合的前 k-1 大值和剩余的部分分。

尝试着理解一次最优化交换的本质。可以发现，最后的答案是二部分的最大值，那么，容易发现，最优化交换其实就是那部分二的最大值交换部分一的最小值，当然了部分一的最小值大于部分二的最小值，就没必要继续交换了。

肯定有人要问，如果这次交换的两个数在同一个集合，那么交换不就不成立了吗，很显然，这种情况是不可能的，至于如何，留作课后作业 如果两个数在同一个集合，那么说明此时部分一的最小值大于部分二的最小值，更没必要交换了。

综合时间复杂度 \mathcal{O}\left(nm\log nm\right).