题解：AT_arc182_d [ARC182D] Increment Decrement Again

Priestess_SLG · 2026-11-09 11:04:50 · 题解

一个比较巧妙的转化是：不考虑取模关系，因为相邻元素不能相等而且更新的时候只能以 1 为单位对单个元素做操作所以相邻元素之间的大小关系永远不会变化。构造序列 C 满足 C_1=B_1，记 \delta=(B_i-B_{i-1})\bmod M 则若 A_{i-1}<A_i 有 C_i=C_{i-1}+\delta 否则有 C_i=C_{i-1}+\delta-M 此时可能的目标序列 D 满足 D_i=C_i+kM 其中 k 在整个序列取值中固定。

固定 k 的值后最少需要操作的次数就是 \sum\limits_{i=1}^n|A_i-C_i-kM|。考虑 k 取什么值的时候上面和式的值最小，经典结论答案单谷且谷值取在中位数区间上，因此求一下中位数两边的两个候选值分别算一遍答案即可。时间复杂度为 O(n\log n) 瓶颈在对序列排序。

corner case 是 m=2 的情况需要特殊处理。

namespace lowspeed_song {

mt19937_64 mt(time(0));

inline void init() {
}

int a[N], b[N], c[N];

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    if (m == 2) cout << (equal(a, a + n, b, b + n) ? 0 : -1) << '\n';
    else { c[0] = b[0];
        for (int i = 1; i < n; ++i) {
            int dlt = (b[i] - b[i - 1] + m) % m;
            if (a[i - 1] < a[i]) c[i] = c[i - 1] + dlt;
            else c[i] = c[i - 1] + dlt - m;
        } vector<int> vec;
        for (int i = 0; i < n; ++i) vec.emplace_back(a[i] - c[i]);
        ranges::sort(vec);
        vector<int> cand = {vec[n / 2] / m - 1, vec[n / 2] / m, vec[n / 2] / m + 1};
        int res = inf;
        for (int &o : cand) {
            int sum = 0;
            for (int i = 0; i < n; ++i) sum += abs(a[i] - c[i] - o * m);
            res = min(res, sum);
        } cout << res << '\n';
    }
}

} // namespace lowspeed_song