题解：P11792 [JOI 2017 Final] JOIOI 王国 / Kingdom of JOIOI

jijidawang · 2025-06-13 18:13:43 · 题解

二分答案 x，由于全局最小值和全局最大值 \min,\,\max 显然不能分在同一边否则不优，那么只有两种情况：

• 分界线左侧的海拔都不小于 {\min}+x，分界线右侧的海拔都不大于 {\max}-x。
• 分界线右侧的海拔都不小于 {\min}+x，分界线左侧的海拔都不大于 {\max}-x。

从而对于每一行来说可以求出能当分界线的区间，接下来需要在每个区间里选一个点组成一个递增 / 递减的点列，这是经典贪心问题可以随意做。

时间复杂度 O(nm\log V)。