绝对值不等式的简易解法

· · 题解

看到这道题目，感觉没有什么很好的性质。

我们发现，序列长度每增大一，就可以获得 k 个“贝”，可以使得 x 或 y 的和变动一。

设 A_p=\sum\limits_{k=1}^px_{k-1},B_p=\sum\limits_{k=1}^py_{k-1}。

当序列长度为 m 时，我们有 mk 个“贝”，需要使用 |\lfloor\dfrac mn\rfloor A_n+A_{m\bmod n}-x|+|\lfloor\dfrac mn\rfloor B_n+B_{m\bmod n}-y| 个贝。

其合法当且仅当上式小于等于 mk，枚举 m\bmod n 的值之后其形如 |ax-b|+|cx-d|\le ex+f 的形式。

枚举两个绝对值的正负性，一共有四种情况，因为合法情况如果将正数取反依旧成立，所以合法当且仅当四种情况均满足。

枚举正负性之后不等式形如 kx\ge y，在分类讨论 k 的正负性即可。

建议大家将 \inf 开大，本题据说只能卡到 5\times10^{17}，我场上开的 10^{18}：

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+100;
using ll=long long;
using ul=unsigned long long;
using LL=__int128_t;
const ll INF=3e18;
int T,n,m,K,X,Y,c[N];
ll a[N],b[N];
LL ans;
LL sol(ll x,ll X,ll y,ll Y,ll s,ll d){
    //|x-kX|+|y-kY|<=ks+d
    ll L=0,R=INF;
    function<void(ll,ll)>run=[&](ll x,ll y){//kx>=y
        if(!x){
            if(y>0)L=INF,R=0;
            return;
        }
        if(x>0){
            if(y>0)L=max(L,(y-1)/x+1);
        }else{
            if(y>0)L=INF,R=0;
            else{
                x=-x,y=-y;
                R=min(R,y/x);
            }
        }
    };
    run(s+X+Y,x+y-d);
    run(s-X+Y,-x+y-d);
    run(s+X-Y,x-y-d);
    run(s-X-Y,-x-y-d);
    // printf("|%lld-%lld*%lld|+|%lld-%lld*%lld|<=%lld*%lld+%lld\n",x,L,X,y,L,Y,L,s,d);
    if(L>R)return INF;
    else return L;
}
int main(){
    freopen("wind.in","r",stdin);
    freopen("wind.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z;
    for(cin>>T;T--;){
        cin>>n>>K>>X>>Y;
        for(x=1;x<=n;++x){
            cin>>a[x]>>b[x];
            a[x]+=a[x-1];
            b[x]+=b[x-1];
        }
        ans=INF;
        for(x=0;x<n;++x){
            LL v=sol((ll)X-a[x],a[n],(ll)Y-b[x],b[n],1ll*K*n,1ll*K*x);
            // cerr<<x<<" "<<ll(v)<<endl;
            ans=min(ans,v*n+x);
        }
        if(ans>1e18)puts("-1");
        else printf("%lld\n",ll(ans));
    }
    return 0;
}