Farmer John's Favorite Operation (USACO Silver 2025 January)

这个题解法简单，但是理解起来不太直观（出题人应该是先想好的解法，再编写题目的），官方题解也写得很绕，所以是一道考验思维能力的题目。下面是一种解释的方法，供参考。

$b_i=a_i \mod M$，然后从小到大排序，然后我们断言$x$在以下数字中：

这个成立的原因如下：

1. 原题要求操作之后的$a_i-x$可以被$M$整除，这个操作的次数就是$\text{ans}=\sum_i f(|a_i-x| \mod M)$，其中$f(y)=\min(y, M-y)$。$f(y)$的意思，就是当$y$小于$M/2$的时候，我们把$(a_i-x) \mod M$移动变成0，而当$y$大于$M/2$的时候，我们把它移动变成$M$，这样可以让操作次数最小。
2. 按这个定义，我们把$a_i$变成$b_i=a_i \mod M$，对于上面1里面的计算是没有影响的:
   $$\begin{align*} \text{ans} &= \sum_i \min(|b_i - x|, M - |b_i - x|) \\ &= \sum_i \min(|b_i - x|, (b_i+M)-x, x-(b_i-M)) \end{align*}$$
   第二步第二第三项，分别当$b_i < x$和$b_i > x$时成立。这三项，分别对应上面“断言”中的三行。
3. 因为随着$x$的变化，整体ans也是线性变化的，所以极值只会取在端点，也就是x只需要取$b_i, b_i+M, b_i-M$这些值。
4. 对于一个具体的$x$，我们观察上面表达式中的三项，分别是$b_i$与$x$的距离，$b_i+M$与$x$的距离，$b_i-M$与$x$的距离。那么最后的ans就是以$x$为中心，上面的数组中上下各$M/2$的范围内的数字与$x$的距离之和。

所以我们只需要在以上范围内枚举$x$，然后计算以$x$为中心，上下$M/2$的范围内的数字与$x$的距离之和（下限$x-M/2$，上限$x-M/2+M$）， 然后取最小值就可以了。使用prefix sum，可以在$\mathcal{O}(n)$时间内完成。再加上排序时间，最后复杂度是$\mathcal{O}(n\log n)$。

（以下程序上实现中，实际只使用了$b_i, b_i+M$这$2n$个值，这个可以证明和这里讲的$3n$个值是一样的，具体证明略过，复杂度一样）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t, n;
ll m;
ll a[400005], b[400005];  // b is prefix sum of a
 
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d%lld",&n, &m);
        for(int i=0;i<n;++i) {
            scanf("%lld", &a[i]);
            a[i] %= m;
        }
        sort(a, a+n);
        for (int i = 0; i < n; i++)
            a[i+n] = a[i] + m;
        for(int i=0;i<2*n;++i) 
            b[i+1] = b[i] + a[i];
        int li = 0, ri = 0;
        ll ans = 1e18;
        for (int i = 0; i < 2*n; i++) {
            ll l = a[i]-m/2;
            ll r = l+m;
            if (l < 0) continue;
            if (r >= 2*m) continue;
            while (a[li] < l) li++;
            while (a[ri] < r && ri < 2*n) ri++;
            ll v = (i-li)*a[i] - (b[i]-b[li]);     // sum of abs(a[j]-a[i]) from li to i-1
            v += (b[ri]-b[i+1]) - (ri-i-1)*a[i];   // sum of abs(a[j]-a[i]) from i+1 to ri
            ans = min(ans, v);
        }
       printf("%lld\n",ans);
    }
    return 0;
}