自动搬运

查看原文

来自洛谷，原作者为

	Noby_Glds be serious

搬运于2025-08-24 22:55:50，当前版本为作者最后更新于2024-03-02 19:09:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先我们把 $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$

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

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

如果有一个 $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;
}