SCP-J 2025
T3 P14259 兄妹(siblings)
每一列的书交给一个人来放是最优的。预处理出每一列的总步数 \(v_i\)。
同时处理横坐标和纵坐标的步数非常不便。我们发现两个人 \(X,Y\) 里面一定有一个横坐标最大会去到最后一列,令他为 \(Y\),那我们枚举 \(X\) 最大取到第 \(i\) 列。那么第 \(i+1\sim maxr\) 列的书都由 \(Y\) 负责,第 \(i\) 列一定由 \(X\) 负责,直接加上。
问题转化成前 \(i-1\) 列有 \(i-1\) 个东西,怎么分配给两个人使得两个人得到的东西价值更大者最小。显然二分。于是问题又转化成 \(i-1\) 个东西,限定每个人最多可以拿 \(mid\) 体积的东西,看能否拿完所有东西。这也是显然的背包。我们让每个物品的价值和体积都为 \(v_i\),背包算一个人最多能拿多少体积的东西,这时当前 \(v\) 的总量减去它就是另一个人要拿的东西总体积,看它拿不拿的下(会不会超过 \(mid\))即可。
这里对于背包,由于枚举每一个 \(i\) 都要看当前的前 \(i-1\) 个物品的情况,所以我们每一次循环就加入一个物品来做一次背包即可。不要每一次循环都整体背包一次,更不要在二分里背包。
枚举的 \(r_{max} \le 5*10^2\),背包用到的 \(sumv \le r_{max}*c_{max}*2=5*10^5\),二分 \(log\),乘起来不超时。(?