P3543 [POI2012]WYR-Leveling Ground

· · 题解

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
*/