P10217 [省选联考 2024] 季风 题解

· · 题解

\textbf{P10217}
  • 给定 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：
  • 特别地，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。

以下令 x_{c},y_c 表示当前的 x,y 值，x,y 特指目标值。

注意到把所有 |x'|,|y'| 的增加放到最后不影响结果，也就是说如果满足 \sum\limits_{i=0}^{m-1}|x_{i}'|+|y_{i}'| \le mk，我们 |x'|,|y'| 的增量就是合法的。

这时答案有单调性，即 m 合法 m' \ge m 的 m' 都合法（你可以通过令 x'=-x,y'=-y 来调整到 x,y）。

注意到一个长度为 n 的完整变化序列 \{x_0,y_0,\ldots,x_{n-1}.y_{n-1}\} 对 x_c,y_c 的影响恒为 sx = \sum x_i,sy = \sum y_i，如果我们钦定 m \bmod n = 0，那么一个 m 的合法条件是 |m \cdot sx - x|+|m \cdot sy - y| \le m \cdot n \cdot k，可以解出若干个区间 m \in [l_i,r_i]，答案就是 n \cdot \min \{l_i\} 。

考虑 m \bmod n \ne 0 的情况，此时我们相当于走了一段循环的一个前缀。令 f = m \bmod n,p = x - \sum \limits_{i=0}^f x_i,q = y - \sum \limits_{i=0}^f y_i，最后 f 次操作即是从 x_c = p,y_c = q 变成 x_c = x,y_c = y，同时还有 (f+1)k 的 |x'|,|y'| 可以使用，也就是我们的不等式为 |m \cdot sx - p|+|m \cdot sy - q| \le (m \cdot n +f+1) \cdot k，解出 m \in [l_i,r_i] 后答案是 n \cdot \min \{l_i\} + f + 1。

我们枚举 f 的值，预处理 x_i,y_i 的前缀和，即可 \mathcal O(n) 完成单组数据。总时间复杂度 \mathcal O(\sum n)。

注意下面代码里下标都从 1 开始，可能式子和上面有一点小区别。

  • 怎么求解不等式 |m \cdot sx - p|+|m \cdot sy - q| \le (m \cdot n+f+1) \cdot k？
  • 这是基础初一数学知识喵。分讨 m \cdot sx - p,m \cdot sy - q 的正负即可。
/**
 *    author: sunkuangzheng
 *    created: 02.03.2024 16:20:32
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
using db = long double;
#define int long long
const int N = 1e5+5;
using namespace std;
ll T,n,d,k,x,y,ax[N],ay[N],ans = 9e18;
void los(){
    cin >> n >> k >> x >> y; ans = 9e18;
    for(int i = 1;i <= n;i ++) cin >> ax[i] >> ay[i],ax[i] += ax[i-1],ay[i] += ay[i-1];
    for(int i = 0;i < n;i ++){
        ll p = x - ax[i],q = y - ay[i];
        ll l = 0,r = 1e18;
        auto fk1 = [&](ll x,ll p){
            if(x < 0) l = max(l,(ll)ceil(1.0 * p / (db)x));
            else if(x > 0) r = min(r,(ll)floor(1.0 * p / (db)x));
            else if(0 > p) l = 1e18,r = 0;
        }; 
        auto fk2 = [&](ll x,ll p){
            if(x > 0) l = max(l,(ll)ceil(1.0 * p / (db)x));
            else if(x < 0) r = min(r,(ll)floor(1.0 * p / (db)x));
            else if(0 < p) l = 1e18,r = 0;
        }; 
        auto upd = [&](){
            if(l <= r) ans = min(ans,l * n + i);
            l = 0,r = 1e18;
        };
        fk2(ax[n],p),fk2(ay[n],q),fk1(ax[n] + ay[n] - n * k,k * i + p + q),upd();
        fk1(ax[n],p),fk2(ay[n],q),fk1(-ax[n] + ay[n] - n * k,k * i - p + q),upd();
        fk2(ax[n],p),fk1(ay[n],q),fk1(ax[n] - ay[n] - n * k,k * i + p - q),upd();
        fk1(ax[n],p),fk1(ay[n],q),fk1(-ax[n] - ay[n] - n * k,k * i - p - q),upd();
    }cout << (ans == 9e18 ? -1 : ans) << "\n";
}signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}