P10217 [省选联考 2024] 季风

· · 题解

感觉自己做法很厉害，就记下来看看：

首先我们把 x_i 和 y_i 无限循环，即 x_i=x_{i\%m+1}，y_i 同理。

题目要求我们求一个最小非负整数 m 使得 |\sum_{i=1}^mx_i-X|+|\sum_{i=1}^my_i-Y|\leq mk

然后很多人就使用二分加分讨，太麻烦了。

直接把绝对值拆了，会有一下四种情况：

\sum_{i=1}^m(x_i+y_i+k)\geq X+Y \sum_{i=1}^m(x_i-y_i+k)\geq X-Y \sum_{i=1}^m(-x_i+y_i+k)\geq -X+Y \sum_{i=1}^m(-x_i-y_i+k)\geq -X-Y

如果有一个 m 满足上面所有的条件，那么这个 m 是合法的（可以自己尝试证明一下）。

接下来我们只针对第一种情况进行分析。

首先设 s_i=\sum_{j=1}^i(x_j+y_j+k)，pos=X+Y。

然后我们发现，如果 s_i+ks_n\geq X+Y，根据 s_n 的取值，k 有不同的范围。

当 s_n>0 时，我们可以获得一个 k 的下界，反之则会获得一个上界。

特别的，当 s_n=0 时，若 s_i\geq X+Y，则 k 可取任意值，否则无解。

当我们对四种情况都进行了一遍求上界（下界）之后，我们的 k 会锁定在一个区间 [l_i,r_i] 内。

也就是说，m=i+kn(l_i\leq k\leq r_i) 都是合法的。

然后枚举 i，如果 l_i\leq r_i，即存在合法区间，那么 ans=\min(ans,i+l_in)。

结束，时间复杂度线性。

（并不需要涉及 abs 和 __int128，避坑了十分舒服）

#include<bits/stdc++.h>
#define N 1000010
#define int long long
using namespace std;
int T,n,k,X,Y,u,v,aim;
int a[N],x[N],y[N],s[N],t[N],l[N],r[N];
void get(int ox,int oy){
    int pos=ox*X+oy*Y;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+ox*x[i]+oy*y[i]+k;
    if(!s[n]){
        for(int i=1;i<=n;i++) if(s[i]<pos) r[i]=-1;
        return;
    }
    for(int i=1;i<=n;i++){
        if(s[n]>0){
            if(s[i]<pos) l[i]=max(l[i],((pos-s[i])%s[n]?(pos-s[i])/s[n]+1:(pos-s[i])/s[n]));
        }
        else{
            if(s[i]<pos) r[i]=-1;
            else r[i]=min(r[i],(pos-s[i])/s[n]);
        } 
    }
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>k>>X>>Y;
        for(int i=1;i<=n;i++) cin>>x[i]>>y[i],l[i]=0,r[i]=1e15;
        if(!X&&!Y){cout<<"0\n";continue;}
        get(1,1),get(1,-1),get(-1,-1),get(-1,1);
        int ans=1e18;
        for(int i=1;i<=n;i++) if(l[i]<=r[i]) ans=min(ans,l[i]*n+i);
        if(ans==1e18) cout<<"-1\n";
        else cout<<ans<<endl;
    }
    return 0;
}