2020年浙江理工大学校赛同步赛 E yesky wine展销会

题目大意

给你n个坐标，你需要让每个坐标的差值为k，你可以移动这些坐标来完成这个目的，请问最少移动多少。

解题思路

看到这个题目的时候。。真的没啥思路。

还好大佬抬我一手。。感谢大佬

当时还有点理解的，后来比赛完之后有人问了我一下这个题目。

被考住了。。还是感觉不够理解，为啥一定是最优解。

后面看到别人博客，自己试着推了一下，感觉自己差不多懂了。

假设，我们先以$k,2k,3k,…,nk$为基准，想要每个点都是这个状态，于是我们可以用每个点的坐标做差，得到每个点的差值$x_i-i*k$，求之前需要对坐标数组进行排序。

得到每个点的差值之后，我们肯定是不能就是按照$k,2k,3k,…,nk$这个基准来，因为我们可以让这些k相关点进行一个移动，至少可以移动到一个点上来，我们就假设以这个点展开，那么这个点就叫做基准点。

那么我们就需要找到这个基准点。

假设存在一些差值，分别是$…,a-bk,c-dk,e-fk,g-hk,i-jk,…$，都是按照大小进行排序的。

假设我们取$c-dk$这个差值，也就是以c为基准点，将其他所有的值，进行偏移$c-dk$。

加入c在dk的左边，即差值为负数，即整体向右移，或者说k相关点向左移。

对于他左边的差值，都是减小$c-dk$的，（这个差值都是取绝对值的，以后省略）。

对于他右边的差值，如果差值小于0的话，也是减小$c-dk$的，如果差值大于0的话，就是增加$c-dk$的。

因为差值减小是取绝对值的，所以可能减小也可能增大，因为他左边的点的差值的绝对值都比他大，所以他左边的点都是差值减小的，他右边的点的差值的绝对值都比他要小，实际上是差值增大的，但是差值增大就是绝对增大的。

如果在c在dk的右边同理，可以得到差不多的结果。

假设c在dk左边，令$c-dk$为$Δx$,他左边的点个数记为$n_1$，右边小于0的点个数记为$n_2$，其他的点个数记为$n_3$。

那么便可以得到减小的值是$n_1\times Δx$，增加的值是$n_2\times (Δx-|x_i|)+n_3\timesΔx$。

假设原本的所有差值的和为s，那么最后得到的结果便是$s+|n_1-(n_2+n_3)|\times Δx-n_2\times |x_i|$。

其中$|n_1-(n_2+n_3) |$就是基准点左右两边的数的个数的差值。

显然，当基准点为中位数的时候，差值为0或者为1。

由于当你取的基准点偏离中位数的时候，显然第一个式子会比第二个式子要大得多，只要我们将增加的值取得最小，也就是最优解了。

当c在dk右边的时候可以得到相类似的结果。

所以我们只需要取中位数即可。

最后的结果就是每个点的差值减去中位数的差值然后取绝对值相加即可。

（可能证明不是很严谨。。但是我也尽力了。

贴一个我认为比较严谨的数学方式证明的链接。

链接。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6+6;
ll x[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	sort(x + 1, x + 1 + n);
	for (ll i = 1; i <= n; i++) {
		x[i] -= i * k;
	}
	sort(x + 1, x + 1 + n);
	ll t = x[(n + 1) / 2];
	for (int i = 1; i <= n; i++)	ans += abs(x[i] - t);
	cout << ans << endl;
	return 0;
}