题目分析

这是 POI 2012 Leveling Ground 的题解代码。题目要求：

• 给定长度为 $n$ 的数组 $h$
• 每次操作可以将一个区间增加/减少 $a$，或者增加/减少 $b$
• 目标是将整个数组变为 $0$
• 求最小操作次数

核心思路

1. 差分转化

代码的关键是将原问题转化为差分数组上的问题：

for (int i = n + 1; i >= 1; i--) {
    h[i] = h[i] - h[i - 1];
    // ...
}

这样区间操作就变成了对两个端点的操作。

2. 数论基础

设 $c = \gcd(a, b)$，只有当所有 $h[i]$ 都能被 $c$ 整除时才有解：

if (h[i] % c != 0) {
    print(-1);
    return 0;
}

3. 扩展欧几里得

对于每个差分值 $h[i]$，求解方程：

使用扩展欧几里得算法：

exgcd(a, b, x[i], y[i]);
x[i] *= h[i] / c;
y[i] *= h[i] / c;

4. 寻找最优解

由于方程有多组解，代码通过调整找到使 $|x| + |y|$ 最小的解：

// 四种调整方式，寻找最优的(x,y)对
p = (x[i] % A + A) % A;
q = (h[i] - p * a) / b;
// ...

5. 贪心调整

最后使用优先队列进行贪心调整，使得总的 $x$ 和为 $0$：

while (sumx != 0) {
    ans -= q.top().first;
    // 调整x[i]和y[i]的值
    // ...
}

复杂度分析

• 扩展欧几里得：$O(\log \min(a,b))$ 每个元素
• 贪心调整：$O(n \log n)$
• 总复杂度：$O(n \log n)$

关键点

1. 差分转化：将区间操作转化为单点操作
2. 通解调整：利用扩展欧几里得的通解形式找到最优解
3. 贪心平衡：通过优先队列平衡总的 $x$ 和

这个解法巧妙地将区间操作问题转化为数论和贪心问题，是竞赛中典型的数学+算法结合题型。