CF433C 【Ryouko's Memory Note】

题意：

给出2个正整数 (n,m(1le n,m le 10^5)) ，接下去给出 (a_1,a_2,cdots a_m(1le a_ile n))

你可以把这个序列里所有值为 (a_i) 的元素改成 (a_j) ((1le i,jle m)) ，注意 (i) 可以等于 (j) ，只可以改一次。

最小化 (sumlimits_{i=1}^{ile m-1} |a_i-a_{i+1}|)

(Solution)

有个性质：有一个数列 (a_1,a_2,cdots a_n) ，取一个元素 (a_x) ，最小化 (sumlimits_{i=1}^{ile n} |a_x-a_{i}|) ,则 (a_x) 为这个数列的中位数。

可以 (O(n)) 预处理出所有与它相邻的数，并且知道一次都不换(或者 i=j的时候的结果)

假设我们已经知道了要替换哪个值，先O(相邻数的个数)跑一遍统计最初的贡献，接着应用上面那个性质，可以知道应该把这个数替换成与它相邻数的序列的中位数，再 O(相邻数的个数) 跑一遍统计现在的贡献，2次贡献作差即为把这个数换掉最多能减小多少。这样跑一次是 O(相邻数的个数*log(相邻数的个数)) 的（因为排序找中位数，带个log）

但是我们并不知道该替换哪个，可是发现被替换的数的值域在枚举的范围内，直接枚举即可。

总的复杂度：(O(mlog m)) ，可以通过。因为相邻数的个数总共 (2m) 个，排序带个log，枚举 (n) 可以忽略不计。

#include <bits/stdc++.h>
using namespace std;
#define rint register int
const int N=100010;
int n,m,a[N];
long long ans,s;
vector<int>v[N];
int main() {
	scanf("%d%d",&n,&m);
	for(rint i=1;i<=m;++i)scanf("%d",&a[i]);
	for(rint i=1;i<m;++i) {
		s+=abs(a[i]-a[i+1]);
		if(a[i]!=a[i+1]) {
			v[a[i]].push_back(a[i+1]);
			v[a[i+1]].push_back(a[i]);
		}
	}
	ans=s;
	long long sum,lst;
	for(rint i=1;i<=n;++i) {
		if(!v[i].size())continue;
		sum=lst=0;
		for(rint j=0;j<v[i].size();++j)
			lst+=abs(i-v[i][j]);
		sort(v[i].begin(),v[i].end());
		int mid=v[i].size()/2;
		for(rint j=0;j<v[i].size();++j)
			sum+=abs(v[i][mid]-v[i][j]);
		ans=min(ans,s-lst+sum);
	}
	printf("%lld
",ans);
	return 0;
}

PS：中位数有个 nth_element 函数，均摊线性，用法可以问百度 ,所以本题其实可以均摊 (O(m)) ，只需要把循环改成这样：

	for(rint i=1;i<=n;++i) {
		if(!v[i].size())continue;
		sum=lst=0;
		for(rint j=0;j<v[i].size();++j)
			lst+=abs(i-v[i][j]);
		int mid=v[i].size()/2;
		nth_element(v[i].begin(),v[i].begin()+mid,v[i].end());
		for(rint j=0;j<v[i].size();++j)
			sum+=abs(v[i][mid]-v[i][j]);
		ans=min(ans,s-lst+sum);
	}

第一次提交的时候代码放错了，请管理员通过一下第2次的，谢谢

upd:发现公式写错了一个地方，已经更改，麻烦管理员了，谢谢！