自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:50:01，当前版本为作者最后更新于2021-12-20 09:09:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

• Update on 2022.9.29：修改表述。
• Update on 2025.1.22：修订。

P3543 [POI2012] WYR-Leveling Ground

区间操作转化为差分数组 $d_i = a_i - a_{i - 1}\ (1\leq i \leq n + 1)$ 的端点操作，其中 $a_{n + 1} = 0$。一次 $+a$ 和一次 $-a$ 抵消，一次 $+b$ 和一次 $-b$ 抵消。设 $A = \frac a d$，$B = \frac b d$。

首先考虑对每个差分值单独求解，解不定方程 $ax + by = d_i$。设 $d = \gcd(a, b)$，根据裴蜀定理，若 $d\nmid d_i$ 则无解。否则用扩欧求得 $ax + by = d$ 的特解，再乘以 $\frac {d_i} d$ 得到 $ax + by = d_i$ 的特解。

先不考虑可行性。因为 $ax_i + by_i = d_i$ 的贡献为 $|x_i| + |y_i|$，而最终答案为所有贡献之和除以 $2$，所以先找到 $|x_i| + |y_i|$ 最小的特解。若 $x_i$ 和 $y_i$ 均不为最小非负整数或最大负整数可行解，则调整法可证 $|x_i| + |y_i|$ 必然不是最优。因此我们只需检查 $x_i$ 和 $y_i$ 分别取到最小非负整数和最大负整数的情况。

当前 $\frac 1 2\sum (|x_i| + |y_i|)$ 是答案的下界，但不能保证可行性，还需满足 $X = \sum x_i = 0$。当 $X = 0$ 时 $Y = 0$，所以只需考虑 $X$。

根据特解的形式

$$\begin{cases} x = x' + kB \\ y = y' - kA \end{cases} $$

当 $X < 0$ 时，我们需要进行 $-\frac X B$ 次将某个 $x_i$ 加上 $B$，并将对应的 $y_i$ 减去 $A$。$\frac X B$ 一定是整数，因为差分数组之和为 $0$。类似的，$X > 0$ 时 $x_i$ 减去 $B$，$y_i$ 加上 $A$。称这样的操作为对 $i$ 进行一次调整，调整的代价等于新的 $|x'_i| + |y'_i|$ 减去原来 $|x_i| + |y_i|$。

容易证明调整一个数的代价随着调整次数增加仅在 $x_i$ 或 $y_i$ 改变符号时增加，其它时候不变，因此我们可以用堆维护这个过程：每次取出代价最小的 $i$ 并弹出，在需求次数与不改变符号的限制下尽可能多地调整。若经过调整后需求次数为 $0$，则算法结束，否则将新的调整代价压入堆。时间复杂度 $\mathcal{O}(n\log n)$，因为 $x_i, y_i$ 中任意一个改变符号才会改变代价，最多发生 $2n$ 次。

一个神奇的性质是 $|\frac X B|$ 在 $\mathcal{O}(n)$ 级别，这使得我们可以从堆中取数时仅进行一次调整就塞回去。证明（来自 评论区）：当 $|x_i| + |y_i|$ 取到最小值时若 $x_i$ 为最小非负整数或最大负整数，则 $|x_i| \leq B$，则 $|X| \leq nB$。若 $y_i$ 为最小非负整数或最大负整数则 $|y_i| \leq A$，即 $\left| \frac {-XA + \sum d_i} {B} \right| \leq nA$，根据 $\sum d_i = 0$ 得 $|X| \leq nB$。

忽略问题限制得到基本解法再调整，巧妙结合反悔贪心和扩展欧几里得。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using uint = unsigned int;
// using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(ll x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 1e5 + 5;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
int n, a, b, c[N], d, ad, bd;
ll u, v, x[N], y[N], dx, ans;
int sgn(ll x) {return x < 0 ? -1 : 1;}
void exgcd(ll a, ll b, ll &x, ll &y) {
  if(!b) return x = 1, y = 0, void();
  exgcd(b, a % b, y, x), y -= a / b * x;
}
priority_queue<pii, vector<pii>, greater<pii>> q;
void ins(int i) {q.push({abs(x[i] - sgn(dx) * bd) + abs(y[i] + sgn(dx) * ad) - abs(x[i]) - abs(y[i]), i});}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n >> a >> b, d = __gcd(a, b);
  ad = a / d, bd = b / d, exgcd(a, b, u, v);
  for(int i = 1; i <= n; i++) c[i] = read();
  for(int i = ++n; i; i--) c[i] -= c[i - 1], x[i] = INF;
  for(int i = 1; i <= n; i++) {
    if(c[i] % d) puts("-1"), exit(0);
    ll p = u * c[i] / d, q = v * c[i] / d, _x, _y;
    auto chk = [&]() {if(abs(_x) + abs(_y) < abs(x[i]) + abs(y[i])) x[i] = _x, y[i] = _y;};
    _x = (p % bd + bd) % bd, _y = (c[i] - _x * a) / b, chk(), _x -= bd, _y += ad, chk();
    _y = (q % ad + ad) % ad, _x = (c[i] - _y * b) / a, chk(), _y -= ad, _x += bd, chk();
    dx += x[i], ans += abs(x[i]) + abs(y[i]);
  }
  for(int i = 1; i <= n; i++) ins(i);
  for(ll i = 0; i < abs(dx); i += bd) {
    pii t = q.top(); q.pop();
    ans += t.fi, x[t.se] -= sgn(dx) * bd, y[t.se] += sgn(dx) * ad, ins(t.se);
  }
  cout << ans / 2 << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/29
author: Alex_Wei
start coding at 19:23
finish debugging at 20:07
*/