题解：P11671 [USACO25JAN] Farmer John's Favorite Operation S

· · 题解

来一发神奇二分做法。

我的整体思路是 O(n) 枚举 x（经过证明，只有 n 种情况），然后 O(\log n) 求出每一种 x 对应的答案。

首先将 a 数组全部对 m 取模，并排序。这样就得到了一个值域为 [0,m-1] 的数组。容易发现，x 一定等于某个 a_i。这样，x 的值域也确定为 [0,m-1]。于是，a_i-x 的值域也确定了：[0-(m-1),(m-1)-0] 即 [-(m-1), m-1]。

我们的目标是把 a_i 变成 m 的倍数，不妨看它的几何意义，即把数轴上移动到最靠近它的 m 倍数点上。又由 a_i-x 的值域可知，最后移动到的 m 倍数点只有三个：-m，0 和 m。这样，我们可以把减去 x 之后，数组中的所有数字从小到大分为五类：

然后就可以通过 lower_bound 和 upper_bound 确定这五类数的区间（由于数组 a 单调递增，这五种数一定对应着数组上五个连续的区间，这五个区间无重叠、无遗漏地从左到右组成了数组 a）。然后分别统计答案：

  1. 答案为 |(a_i-x)-(-m)|=a_i-x+m，三项拆贡献分别计算。
  2. 答案为 |(a_i-x)-0|=x-a_i，两项拆贡献分别计算。
  3. 答案为 0。
  4. 答案为 |(a_i-x)-0|=a_i-x，两项拆贡献分别计算。
  5. 答案为 |(a_i-x)-(-m)|=m - a_i + x，三项拆贡献分别计算。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2e5 + 10;
ll T, n, m, a[2 * N], s[2 * N];
inline ll calc(ll x) {
    return min(x % m, m - x % m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
            a[i] = (a[i] % m);
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i ++) {
            s[i] = s[i - 1] + a[i];
        }
        ll ans = 1e18;
        for (int i = 1; i <= n; i ++) {
            if (i != 1 && a[i] == a[i - 1]) continue;
            ll x = a[i], tmp = 0;
            ll idx = upper_bound(a + 1, a + n + 1
            , floor((2.0 * x - 1.0 * m) / 2.0)) - a - 1;
            if (idx > 0) {
                tmp += s[idx] - idx * x + idx * m;
            }
            if (idx + 1 <= i - 1) {
                tmp += abs(s[i - 1] - s[idx] - (i - 1 - idx - 1 + 1) * x);
            }
            ll idx2 = upper_bound(a + 1, a + n + 1, x) - a;
            ll idx3 = upper_bound(a + 1, a + n + 1
            , floor((2.0 * x + 1.0 * m) / 2.0)) - a - 1;
            if (idx2 <= idx3) {
                tmp += s[idx3] - s[idx2 - 1] - (idx3 - idx2 + 1) * x;
            }
            if (idx3 + 1 <= n) {
                tmp += m * (n - idx3) - (s[n] - s[idx3] - x * (n - idx3));
            }
            ans = min(ans, tmp);
        }
        cout << ans << "\n";
    }
    return 0;
}