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

· · 题解

题解

简单分析一下题目，发现 x 是什么并不重要，或者说 x 就是我们要去探究的东西。 x 告诉我们，只要满足所有的数关于 M 同余即可（余数就是 x ）。于是想到将所有数直接放到模 M 意义下处理，将“操作为同余”转化为“操作为同一个数”。

将所有数随意转化为同一个数（下称转化数，即 x ），求花费和最小，其实就是货仓选址问题。结论是直接选中位数（若有偶数个元素，则最中间两个元素间任意一个数都可以）作为转化数，证明如下：

先讨论元素个数为奇数情况。设选定的转化数左边有 a 个元素，右边有 b 个，当转化数为中位数时，有 a=b 。

若向左移动一个数，则 b>a 。同时所有转化数左边的元素贡献减一，右边的贡献加一，即总贡献加上了 b-a>0 ，不如放在中位数。往右同理。所以选择中位数是最佳方案。

对于元素个数为偶数情况，因为转化数放在任意两元素间，两元素创造的贡献和恒定，即两元素距离。所以可以将中间两元素看做一个点，转化为奇数情况。在具体处理时，直接选取两元素的任意一个作为转化数即可。

然而本题稍微特殊一些，因为在模 M 意义下讨论，一个数既可以变小也可以变大，都能到达同余值，即所有元素都在一个环上，每个数都可以做中位数。所以要断环成链处理，统计可以用前缀和优化。具体实现可以看代码（虽然写的有点抽象）。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n,m;
int a[200010],b[400010],pre[400010];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T; 
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]%m;
        int ans=1e18;
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++) b[i+n]=b[i]+m;//断环成链处理 
        for(int i=1;i<=2*n;i++) pre[i]=pre[i-1]+b[i];//前缀和优化 
        for(int i=1;i<=n;i++){
            int pos=(n/2)+(n%2==1)+i-1;//找中位数位置，分类讨论奇偶 
            int qian=(pos-i)*b[pos]-(pre[pos-1]-pre[i-1]);
            int hou=(pre[i+n-1]-pre[pos])-(i+n-pos-1)*b[pos];
            ans=min(ans,qian+hou);
        }
        cout<<ans<<endl;
    }
    return 0;
}