World Tour Finals 2019 D - Distinct Boxes 题解

太神了，专门写一篇题解 qwq

简要题意：给你 RR 个红球和 BB 个蓝球，你要把它们放到 KK 个箱子里，要求没有两个箱子完全相同（即两种球个数就相同），求 KK 的最大值。

设第 ii 个箱子中有 xixi 个红球，yiyi 个蓝球，就变成了找平面上一个大小最大的点集 (xi,yi)(xi,yi)，使 ∑xi=R,∑yi=B∑xi=R,∑yi=B。进一步，由于可以直接将 xx 最大的点 xx 坐标变大，yy 同理，因此只需有 ∑xi≤R,∑yi≤B∑xi≤R,∑yi≤B 即可。

这是一道二维平面上的题，我们可以想办法把它变成一维。给 xx 方向赋一个权重 pp，yy 方向赋一个权重 qq，那么一个点 (x,y)(x,y) 就被投影到了 px+qypx+qy 上。此时我们发现所有点投影后的权重和为 ∑pxi+qyi=p∑xi+q∑yi∑pxi+qyi=p∑xi+q∑yi，于是当 ∑xi≤R,∑yi≤B∑xi≤R,∑yi≤B 时，便有 ∑pxi+qyi≤pR+qB∑pxi+qyi≤pR+qB。在某种程度上，我们就会希望 ∑pxi+qyi 尽量小。

首先当然二分 K，问题变为判定一个 K 是否可行。然后我们考虑一个凸包，凸包上的点 (X,Y) 代表 ∑xi=X 时，∑yi 的最小值为 Y。感性理解一下这玩意大概就是凸的，并且对每个 X 都有定义。于是 K 可行当且仅当点 (R,B) 在凸包上方。又发现对于一个 (p,q)，使 p∑xi+q∑yi 最小时，(∑xi,∑yi) 一定在凸包上，于是我们尝试用 (p,q) 搞出凸包上的一些点。

继续发现 p∑xi+q∑yi=(p,q)⋅(∑xi,∑yi)，即向量 (xi,yi) 在向量 (p,q) 上的投影。p∑xi+q∑yi 最小，就是这个投影最小，可以看作拿一条与向量 (p,q) 垂直的直线去切这个凸包，所以每个点都一定有机会被切到，且 (p,q) 的斜率越大，切到的点越偏右。于是再对 (p,q) 的斜率进行二分，如果发现求出来的点 (∑xi,∑yi) 在 (R,B) 左下方，那就成了；如果在 (R,B) 右上方，那就寄了；如果在左上方，那就增大斜率；如果在右下方，那就减小斜率。

这里有两个技巧：1，不要在实数域上二分 (p,q) 的斜率，令 p+q=109+7（或其它常数），然后直接二分 p，可以发现这样基本上能覆盖到所有的斜率都能被弄到，从而能切到每个点。2，由于凸包上相邻两条线段斜率可能非常相近，因此我们要当发现当前凸包上一条连线在 (R,B) 下方时直接返回合法。

最后的问题是如何计算对于一个 (p,q) 计算 p∑xi+q∑yi 的最小值。我们二分一个 z，求出 p∑xi+q∑yi≤z 的个数进行二分。然后求出 p∑xi+q∑yi≤z 的 x,y 分别的和以及多余的一些 p∑xi+q∑yi=z+1 的前若干个 x,y 的和。以上操作全部用类欧做就是一个 log，或者发现如果我们选了一个点 (x,y)，那么它左下角的所有点都一定已经被选了，所以有 min(x,y)≤O(W13)（W 为值域），二维分别枚举即可。

一共三个二分，最后一步用类欧时间复杂度就 O(log4W)，直接枚举复杂度就 O(W13log3W)。