自动搬运

查看原文

来自洛谷，原作者为

	fanminghao000 于万人中万幸得以相逢，刹那间澈净明通

搬运于2025-08-24 23:09:21，当前版本为作者最后更新于2025-02-05 20:45:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

简单分析一下题目，发现 $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;
}