题解：P3543 [POI 2012] WYR-Leveling Ground

· · 题解

题意

给一个序列，序列中可以做若干次区间加减 a 或 b 的操作，问至少多少次操作可以使序列变为全 0 或判无解。

解法

首先因为当 a,b 不互质时只有所有数是 \gcd(a,b) 的倍数才有可能有解，所以可以将所有数除以 \gcd(a,b)，这样后续的过程中，我们都可以认为 \gcd(a,b) = 1，也默认 a < b。

其次，区间操作不好处理，这时我们考虑使用差分，同样目标是化为全 0 序列，但是这样我们的过程将更方便，因为操作转化为一个元素加另一个元素减，将改变量为 a,b 的分开，可以发现答案相当于在改变和为 0 的情况下取绝对值和的一半。

我们先用扩欧求出 x_i,y_i，也就是 i 号元素转化为 0 的一组解，发现单元素中取 x_i \bmod b 或 x_i \bmod b - b 绝对值和最小，那就都设成 x_i 取最小正整数的解，此时 x_i 和不小于 0，会将 x_i 向下调整，接下来就是用 set 维护调整带来的额外代价，通过贪心将 x_i 的和调成 0，此时 y_i 和也会是 0，易得调整是 \operatorname{O}(n) 的。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b,d,p[100009],o[100009];
long long x[100009],y[100009],X,ans;
int gcd(int x,int y){
    return y == 0 ? x : gcd(y,x % y);
}
int exgcd(int a,int b,long long &x,long long &y){
    if(b == 0){
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a % b,y,x);
    y -= a / b * x;
    return d;
}
set<pair<int,int> >s1,s2;
int main(){
    scanf("%d %d %d",&n,&a,&b);
    int d = gcd(a,b);
    a /= d,b /= d;
    if(a > b)
        swap(a,b);
    for(int i = 1; i <= n + 1; i ++){
        if(i <= n)
            scanf("%d",&o[i]);
        p[i] = o[i] - o[i - 1];
        if(p[i] % d != 0){
            printf("-1\n");
            return 0;
        }
        else
            p[i] /= d; 
        exgcd(a,b,x[i],y[i]);
        x[i] = (1ll * x[i] * p[i] % b + b) % b;
        y[i] = (1ll * p[i] - 1ll * x[i] * a) / b;
        X += x[i];
        //printf("%d %d\n",x[i],y[i]);
        ans += abs(x[i]) + abs(y[i]);
        s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
        s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
    }

    while(X != 0){
        //printf("%lld\n",X);
        if(X > 0){
            auto t = *s2.begin();
            s2.erase(s2.begin());
            int i = t.second;
            s1.erase(s1.find(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i)));
            ans += t.first;
            x[i] -= b;
            y[i] += a;
            s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
            s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
            X -= b; 
        }
        else{
            auto t = *s1.begin();
            s1.erase(s1.begin());
            int i = t.second;
            s2.erase(s2.find(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i)));
            ans += t.first;
            x[i] += b;
            y[i] -= a;
            s1.insert(make_pair((abs(x[i] + b) + abs(y[i] - a)) - (abs(x[i]) + abs(y[i])),i));
            s2.insert(make_pair((abs(x[i] - b) + abs(y[i] + a)) - (abs(x[i]) + abs(y[i])),i));
            X += b;
        } 
    }
    printf("%lld\n",ans >> 1);
}