蒟蒻今天做了一套模拟题 , 里面有道题大概是这个样子的:

要把${N}$个重量分别为${Ai}$的物品运到河对面 , 每次你会从最重的一个物品开始选 , 到负载量装不下为止.给定一个数${K}$,要求在最多${K}$趟中 , 能将所有物品均运过河岸.求此时的最小船负载量.(${N ,K <= 2000)}$

蒟蒻看到这个题 , 直接就想到了二分 , 因为显而易见 , 对于任意可行的负载量${S}$ , 比${S}$大的答案一定是可行而差的 ; 比${S}$小的可行答案一定是更优的.(check函数随便瞎搞 , n ^ 2复杂度都可以接受)于是就花了半个小时切了这道题.

然鹅这是错误的

这样的作法会裂开(100 -> 79) , 因为并不是所有情况都满足单调性 , 事实上这相当于一个限定容量 , 选择物品顺序的多次DP背包的操作 , 经过机房dalao的讨论 , 我接受了这样的想法 , 并且事实证明单调性并不一定存在 , 二分的做法是错误的 , 补救的办法是答案一定在二分结果的左侧不大于最大物品重量的区间内 , 扫一遍找最小答案 , 就可以过了(如果复杂度够优秀的话).

可是蒟蒻并没有很理解上述的做法

Q1. 为什么会不符合单调性?尽管可以从背包的角度思考 , 可是很难举出反例 , 这样不明显的五单调性要如何判断

Q2. 为什么答案一定在上述区间中?

蒟蒻晚上想了近一小时并没有什么进展 (甚至拿暴力算法挂机造数据试图找到反例 , 却并没有成功)

求dalao解答~QwQ