[省选联考 2024] 季风
Description
给定 \(n,k,x,y\) 和 \(2n\) 个整数 \(x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}\)。
找到最小的非负整数 \(m\)，使得存在 \(2m\) 个实数 \(x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'\) 满足以下条件，或报告不存在这样的 \(m\)：
- \(\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})=x\)；
- \(\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y\)；
- \(\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k\)。
特别地，\(m=0\) 时，认为 \(\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})\) 和 \(\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})\) 均为 \(0\)。
Solution
我很唐，写了三个多小时。
在坐标系中看问题。注意到如果把 \((x'_i, y'_i)\) 看成点，那么所有点都满足条件 \(|x'_i| + |y'_i| \le k\)，等价于所有点都在一个以坐标系原点为中心的，对角线长 \(2k\) 的 \(45 ^ {\circ}\) 倾斜的正方形中。
假设我们现在枚举了一个 \(m\)，并且算出了 \(\sum_{i = 0} ^ {m - 1} x_{i \bmod n}\) 和 \(\sum_{i = 0} ^ {m - 1} y_{i \bmod n}\)，分别设为 \(tx\) 和 \(ty\)。
那么平均下来每个 \(x'_i\) 和 \(y'_i\) 应该分别要达到 \(\large\frac{x - tx}{m}, \large\frac{y - ty}{m}\)。
那么有结论，如果 \(m\) 满足题目条件，那么一定有 \(\left|\frac{x - tx}{m}\right| + \left|\frac{y - ty}{m}\right| \le k\)。因为我们希望让平均坐标为 \(\left(\frac{x - tx}{m}, \frac{y - ty}{m}\right)\) 的若干个点都在一个封闭图形中，那么最优方案一定是将这些点都集中在平均坐标上，这样它们占的面积最小。而如果连这种最优方案都不满足，那么一定没有方案满足题目的条件的。
将 \(m\) 拆分成 \(xn + b \ (x, b \in N, b \in[0, n) \ )\) 的形式。为了简便，下面设 \(a = n\)。枚举 \(b\)。分别设 \(sx_i, sy_i\) 为 \(x\) 和 \(y\) 数组的前缀和。
那么 \(tx = a\cdot sx_n + sx_b, ty = a\cdot sy_n + sy_b\)。
设 \(p = -sx_n, q = -sy_n, c = x - sx_b, d = y - sy_b\)，那么对于每个 \(b\)，题目就转换为了求下面的不等式的解集。
\[\left| \frac {px + c}{ax + b} \right| + \left| \frac {qx + d}{ax + b} \right| \le k \]\(ax + b\) 恒大于 \(0\)，所以可以分类讨论 \(px + c\) 和 \(qx + d\) 的符号，分四类讨论，把绝对值拆开。
下面以 \(px + c \ge 0, qx + d \ge 0\) 为例。继续推下去。
\[\begin {aligned} \left| \frac {px + c}{ax + b} \right| + \left| \frac {qx + d}{ax + b} \right| \le k \\ \frac {(p + q)x + (c + d)}{ax + b} \le k \\ (p + q)x + (c + d) \le akx + bk \\ (p + q - ak)x + (c + d - bk)\le 0 \end {aligned} \]设 \(r\) 为 \(p + q - ak\)，\(s\) 为 \(c + d - bk\)，那么又转化成了不等式 \(rx + s \le 0\) 的形式。这个不等式方程是很好解的。最后求出解集和 \((0, +\infty)\) 的交集，取解集中最小的数就可以求出这种情况下最小的 \(x\)，进而得到 \(m = ax + b\)。
另外三类情况同理。分类讨论完取四类情况的最小值就是对于当前 \(b\) 的最小 \(m\) 值。
对于所有的 \(b\) 算一遍，这题就做完了。时间复杂度 \(O(n)\)。
代码实现方面，实现一个求 \(ax + b \ge 0\) 的函数，就非常好写了。
标签：P10217,le,frac,题解,sum,right,ax,联考,left From： https://www.cnblogs.com/AzusidNya/p/18052815