P10217 [省选联考 2024] 季风 题解
初步化简题目
注：本篇题解的所有下标均从 \(1\) 开始。
设 \(sumx_h\) 表示 \(\sum_{i=1}^{h}{x_i}\)，\(sumy_i\) 表示 \(\sum_{i=1}^{h}{y_i}\)。
于是题目给出的三个公式可以转化为：
- \((\sum_{i=1}^{m}{x_{i}^{′}}) + sumx_{[(m-1)\mod n]+1} + sumx_{n} \times \left\lfloor\frac{m}{n}\right\rfloor = x\)。
- \((\sum_{i=1}^{m}{y_{i}^{′}}) + sumy_{[(m-1)\mod n]+1} + sumy_{n} \times \left\lfloor\frac{m}{n}\right\rfloor = y\)。
- \(∀1\le i \le m，|x_{i}^{′}| + |y_{i}^{′}| \le k\)。
再移项，得到：
- \((\sum_{i=1}^{m}{x_{i}^{′}}) = x - sumx_{[(m-1)\mod n]+1} - sumx_{n} \times \left\lfloor\frac{m}{n}\right\rfloor\)。
- \((\sum_{i=1}^{m}{y_{i}^{′}}) = y - sumy_{[(m-1)\mod n]+1} - sumy_{n} \times \left\lfloor\frac{m}{n}\right\rfloor\)。
- \(∀1\le i \le m，|x_{i}^{′}| + |y_{i}^{′}| \le k\)。
中途思路
看前两个公式，下标有取模运算，且有负数，感觉直接二分 \(m\) 不太行。
这个 \([(m-1)\mod n]+1\) 看着就很不顺眼，考虑暴力枚举它！
可还是没有用，试着进一步化简题目。
进一步化简题目
三个公式太麻烦，直接合三为一！
\(x_{i}^{′}\) 和 \(y_{i}^{′}\) 都是自己确定且都为 实数，能不能把这两个变量消掉？
根据前面两个公式，再暴力枚举出 \([(m-1)\mod n]+1\)，显然 \((\sum_{i=1}^{m}{x_{i}^{′}})\) 和 \((\sum_{i=1}^{m}{y_{i}^{′}})\) 的正负都确定，我们可以根据这个来规定 \(x_{i}^{′}\) 和 \(y_{i}^{′}\) 的正负（包含 0），成功消掉第三个公式中的绝对值。
我们可以将这三个公式看作一个名额分配的限制，那么有 \(mk\) 个名额分配给 \(|(\sum_{i=1}^{m}{x_{i}^{′}})|\) 和 \(|(\sum_{i=1}^{m}{y_{i}^{′}})|\)（同时别忘记了实数）。
于是成功合三为一！得到限制：\(|(\sum_{i=1}^{m}{x_{i}^{′}})| + |(\sum_{i=1}^{m}{y_{i}^{′}})| \le mk\)。
再代入，得到限制：\(|x - sumx_{[(m-1)\mod n]+1} - sumx_{n} \times \left\lfloor\frac{m}{n}\right\rfloor| + |y - sumy_{[(m-1)\mod n]+1} - sumy_{n} \times \left\lfloor\frac{m}{n}\right\rfloor| \le mk\)。
最后思路
如果你看到这个公式后还在思考二分那你就太落后了，两个绝对值，相信你一定想到了分类讨论 \(4\) 种情况。
既然枚举了 \([(m-1)\mod n]+1\)，那么我们就可以试着求 \(\left\lfloor\frac{m}{n}\right\rfloor\) 的取值范围（因为这两个东西可以合并出 \(m\)）。
设 \(d = \left\lfloor\frac{m}{n}\right\rfloor，f=[(m-1)\mod n]+1\)。
公式又可以化简：\(|x - sumx_{f} - sumx_{n} \times d| + |y - sumy_{f} - sumy_{n} \times d| \le d \cdot n \cdot k + f \cdot k\)。
然后你就要开始快乐的分类讨论了（注意分类讨论之后还不能只按照这一个限制约束，还有其本身的正负限制约束）。
接下来举个例子：
我们规定 \((\sum_{i=1}^{m}{x_{i}^{′}})\le 0\) 且 \((\sum_{i=1}^{m}{y_{i}^{′}})\le 0\)，且已经枚举出 \(f\)，那么公式可以经过如下变换：
- \(sumx_{f} + sumx_{n} \times d + sumy_{f} + sumy_{n} \times d \le (d \cdot n + f) \cdot k + x + y\)
- \(d(sumx_{n} + sumy_{n}) - dnk \le fk + x + y - sumx_{f} - sumy_{f}\)
- \(d(sumx_{n} + sumy_{n} - nk) \le fk + x + y - sumx_{f} - sumy_{f}\)
现在不可以轻易把 \((sumx_{n} + sumy_{n} - fn)\) 除过去，因为这是不等式，需要判断正负来判断是否变号。
同时，\(d\) 的限制不止这一条，同时还需要满足 \(x - sumx_{f} - sumx_{n} \times d \le 0\) 且 \(y - sumy_{f} - sumy_{n} \times d \le 0\)。
公式比较多，实现起来比较复杂，所以写代码时要细心些。
还有，如果你想要复制，那就请你仔细检查自己某一种情况的代码，否则出错会导致你调试的时间翻倍，再翻倍。比如本人就是考场上写着玩意写了两个半小时，每次调试都要 \(4\) 种情况全调一遍。
时间复杂度：\(O(\sum{n} \times 大常数)\)。
Code
这里贴上本蒻的赛时代码，在任何地方测都能 AC。
#include <bits/stdc++.h> // fenleitaolun
using namespace std;
using LL = long long;
const int MAXN = 1e5 + 3;
const LL Inf = 1e18 + 555;
int uid = 0;
int n;
LL sum[2][MAXN], k, X, Y, w;
LL ab(LL x){ return max(x, -x); }
void work(){
cin >> n >> k >> X >> Y;
for(int i = 1; i <= n; i++){
LL x, y;
cin >> x >> y;
sum[0][i] = sum[0][i - 1] + x, sum[1][i] = sum[1][i - 1] + y;
}
w = sum[0][n] + sum[1][n];
if(X == 0 && Y == 0){
cout << 0 << "\n";
return;
}
// |i/n*sum[n] + sum[(i-1)%n+1] - X| + ... <= i * k
LL ans = Inf;
for(int i = 1; i <= n; i++){
LL _x = sum[0][i] - X, _y = sum[1][i] - Y, z = 0;
LL l1, r1, l2, r2, L, R;
// first: >=0 >=0
z = 1ll * i * k - _x - _y, w = sum[0][n] + sum[1][n];
r1 = r2 = 1e18;
if(sum[0][n] > 0){
l1 = (_x >= 0 ? 0 : (-_x + sum[0][n] - 1) / sum[0][n]);
}else l1 = (_x >= 0 ? 0 : Inf), r1 = (_x >= 0 && sum[0][n] < 0 ? _x / (-sum[0][n]) : (_x < 0 ? -1 : 1e18));
if(sum[1][n] > 0){
l2 = (_y >= 0 ? 0 : (-_y + sum[1][n] - 1) / sum[1][n]);
}else l2 = (_y >= 0 ? 0 : Inf), r2 = (_y >= 0 && sum[1][n] < 0 ? _y / (-sum[1][n]) : (_y < 0 ? -1 : 1e18));
L = max(l1, l2), R = min(r1, r2);
if(w - k * n > 0) R = (z < 0 ? L - 1 : min(R, ab(z) / (w - k * n) * (z < 0 ? -1 : 1)));
else if(w - k * n < 0) L = max(L, (ab(z) + ab(w - k * n) - 1) / ab(w - k * n) * (z > 0 ? -1 : 1));
else if(z < 0) L = Inf;
if(L <= R) ans = min(ans, L * n + i);
// second: <=0 >=0
z = 1ll * i * k + _x - _y, w = - sum[0][n] + sum[1][n];
r1 = r2 = 1e18;
if(sum[0][n] < 0){
l1 = (_x <= 0 ? 0 : (_x + (-sum[0][n]) - 1) / (-sum[0][n]));
}else l1 = (_x <= 0 ? 0 : Inf), r1 = (_x <= 0 && sum[0][n] > 0 ? (-_x) / (sum[0][n]) : (_x > 0 ? -1 : 1e18));
if(sum[1][n] > 0){
l2 = (_y >= 0 ? 0 : (-_y + sum[1][n] - 1) / sum[1][n]);
}else l2 = (_y >= 0 ? 0 : Inf), r2 = (_y >= 0 && sum[1][n] < 0 ? _y / (-sum[1][n]) : (_y < 0 ? -1 : 1e18));
L = max(l1, l2), R = min(r1, r2);
if(w - k * n > 0) R = (z < 0 ? L - 1 : min(R, ab(z) / (w - k * n) * (z < 0 ? -1 : 1)));
else if(w - k * n < 0) L = max(L, (ab(z) + ab(w - k * n) - 1) / ab(w - k * n) * (z > 0 ? -1 : 1));
else if(z < 0) L = Inf;
if(L <= R) ans = min(ans, L * n + i);
// third: >=0 <=0
z = 1ll * i * k - _x + _y, w = sum[0][n] - sum[1][n];
r1 = r2 = 1e18;
if(sum[0][n] > 0){
l1 = (_x >= 0 ? 0 : (-_x + sum[0][n] - 1) / sum[0][n]);
}else l1 = (_x >= 0 ? 0 : Inf), r1 = (_x >= 0 && sum[0][n] < 0 ? _x / (-sum[0][n]) : (_x < 0 ? -1 : 1e18));
if(sum[1][n] < 0){
l2 = (_y <= 0 ? 0 : (_y + (-sum[1][n]) - 1) / (-sum[1][n]));
}else l2 = (_y <= 0 ? 0 : Inf), r2 = (_y <= 0 && sum[1][n] > 0 ? (-_y) / (sum[1][n]) : (_y > 0 ? -1 : 1e18));
L = max(l1, l2), R = min(r1, r2);
if(w - k * n > 0) R = (z < 0 ? L - 1 : min(R, ab(z) / (w - k * n) * (z < 0 ? -1 : 1)));
else if(w - k * n < 0) L = max(L, (ab(z) + ab(w - k * n) - 1) / ab(w - k * n) * (z > 0 ? -1 : 1));
else if(z < 0) L = Inf;
if(L <= R) ans = min(ans, L * n + i);
// fourth: <=0 <=0
z = 1ll * i * k + _x + _y, w = - sum[0][n] - sum[1][n];
r1 = r2 = 1e18;
if(sum[0][n] < 0){
l1 = (_x <= 0 ? 0 : (_x + (-sum[0][n]) - 1) / (-sum[0][n]));
}else l1 = (_x <= 0 ? 0 : Inf), r1 = (_x <= 0 && sum[0][n] > 0 ? (-_x) / (sum[0][n]) : (_x > 0 ? -1 : 1e18));
if(sum[1][n] < 0){
l2 = (_y <= 0 ? 0 : (_y + (-sum[1][n]) - 1) / (-sum[1][n]));
}else l2 = (_y <= 0 ? 0 : Inf), r2 = (_y <= 0 && sum[1][n] > 0 ? (-_y) / (sum[1][n]) : (_y > 0 ? -1 : 1e18));
L = max(l1, l2), R = min(r1, r2);
if(w - k * n > 0) R = (z < 0 ? L - 1 : min(R, ab(z) / (w - k * n) * (z < 0 ? -1 : 1)));
else if(w - k * n < 0) L = max(L, (ab(z) + ab(w - k * n) - 1) / ab(w - k * n) * (z > 0 ? -1 : 1));
else if(z < 0) L = Inf;
if(L <= R) ans = min(ans, L * n + i);
}
cout << (ans > 1e18 ? -1 : ans) << "\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
freopen("wind.in", "r", stdin);
freopen("wind.out", "w", stdout);
int T;
cin >> T;
while(T--){
uid++, work();
}
return 0;
}