题解：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$ 之后，数组中的所有数字从小到大分为五类：

$-m < a_i-x < 0$ ，且到 $-m$ 的距离更近，此时有 $|(a_i-x) - (-m)| < |(a_i-x) - 0|$ ，解得 $a_i<\cfrac{2x-m}{2}$ 。
$-m < a_i-x < 0$ ，且到 $0$ 的距离更近，此时有 $|(a_i-x) - (-m)| \geq |(a_i-x) - 0|$ ，解得 $a_i\geq \cfrac{2x-m}{2}$ 。
$a_i-x=0$ 。
$0<a_i-x<m$ ，且到 $0$ 的距离更近，此时有 $|(a_i - x) - 0| < |(a_i - x) - m|$ ，解得 $a_i<\cfrac{2x+m}{2}$ 。
$0<a_i-x<m$ ，且到 $m$ 的距离更近，此时有 $|(a_i - x) - 0| \geq |(a_i - x) - m|$ ，解得 $a_i\geq \cfrac{2x+m}{2}$ 。

然后就可以通过 lower_bound 和 upper_bound 确定这五类数的区间（由于数组

a

单调递增，这五种数一定对应着数组上五个连续的区间，这五个区间无重叠、无遗漏地从左到右组成了数组

a

）。然后分别统计答案：

答案为 $|(a_i-x)-(-m)|=a_i-x+m$ ，三项拆贡献分别计算。
答案为 $|(a_i-x)-0|=x-a_i$ ，两项拆贡献分别计算。
答案为 $0$ 。
答案为 $|(a_i-x)-0|=a_i-x$ ，两项拆贡献分别计算。
答案为 $|(a_i-x)-(-m)|=m - a_i + x$ ，三项拆贡献分别计算。

CPP

#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;
}

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

文章操作

相关推荐

评论

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