自动搬运

查看原文

来自洛谷，原作者为

	jijidawang And in that light, I find deliverance.

搬运于2025-08-24 23:10:16，当前版本为作者最后更新于2025-06-13 18:13:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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