cf433c-ti-jie

CF433C

思路

出于习惯，调换 $n$ 和 $m$，$n$ 为数组长度，$m$ 为值域。

考虑枚举被替换的 $a_i$。枚举值域 $1$ 到 $m$ 的权值 $x$。

每个权值为 $x$ 的点 $a_i$ 的贡献是 $\mid a_i-a_{i-1} \mid+\mid a_i-a_{i+1} \mid$。由于 $a_i$ 被更改，贡献会随之变化，与之有关的是所有 $a_i$ 的左右两边的点。将这些点全部放进 vector 里。设 $p_x$ 表示所有这样的点。

如果要把 $x$ 改为 $y$ 并令 $ans$ 最小，受影响的是 $\sum \mid x-p_{i,j} \mid$ 变为 $\sum \mid y-p_{i,j} \mid$，要使 $\sum \mid y-p_{i,j} \mid$ 最小。

由 $\textbf{初一}$ 知识，当取 $y$ 为 $p_{i,0}$ 到 $p_{i,len}$ 的中位数时，式子最小。一开始我以为是平均数，整半天。

用最开始算出的不修改答案 $num$ 减去 $\sum \mid x-p_{i,j} \mid$ 加上 $\sum \mid y-p_{i,j} \mid$ 得到修改 $x$ 的最小答案，再取最小值。

code

int n,m,a[maxn],ans,num;
vector<int> p[maxn];
int sum,x,sum1;

int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	m=read();n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(i!=1)num+=abs(a[i]-a[i-1]);
	}
	for(int i=1;i<=n;i++){
		if(a[i-1]&&a[i-1]!=a[i])p[a[i]].push_back(a[i-1]);
		if(a[i+1]&&a[i+1]!=a[i])p[a[i]].push_back(a[i+1]);
	}
	ans=num;
	for(int i=1;i<=m;i++){
		if(p[i].size()){
			sort(p[i].begin(),p[i].end());
			sum=sum1=0;x=p[i][p[i].size()/2];
			for(int j=0;j<p[i].size();j++){
				sum+=abs(i-p[i][j]);
				sum1+=abs(x-p[i][j]);
			}
			ans=min(ans,num-sum+sum1);
		}
	}
	printf("%lld\n",ans);
}