自动搬运

查看原文

来自洛谷，原作者为

	blm_xxc 十年OI一场空，不开long long见祖宗

搬运于2025-08-24 23:17:19，当前版本为作者最后更新于2025-06-08 22:13:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

考虑贪心。

题目要求求出将序列 $A$ 所有元素均变为 $−10^9$ 的最小代价，可以分类讨论，主要有以下四种情况：

1. 一次直接将整个区间赋值为 $-10^9$；
2. 先将区间的两端赋值为 $-10^9$，再将整个区间赋值为$-10^9$；
3. 将区间分为两段，每段分别赋值为 $-10^9$；
4. 将区间分为三段，每段分别赋值为 $-10^9$；

容易证明，若将区间分为四段及以上，则肯定不如上述的第二种情况。所以只需将四种情况分别讨论，取最优解即可。

如何实现？

设数组 $a$ 为原来的排列，建立另外四个数组 $b$、$c$、$d$、$e$，其中：

• $b[i]=|a[i]-a[1]|$；
• $c[i]=|c[i]-c[n]|$；
• $d[i]=\min(d[i+1],c[i])$，且 $d[n]=+\infty$（代码中可以赋值为 $10^9$ 之类的大数）；
• 若 $d[i]=c[i]$，则 $e[i]=i$；否则 $e[i]=e[i+1]$。

可以通过这五个数组来表示每种情况的花费。

1. 情况一：花费为 $|a[n]-a[1]|+n$。
2. 情况二：花费为 $\min \limits^{n-2}_{i=2}{(b[i]+d[i+1]+n+2)}$。
3. 情况三：花费为 $\min \limits^{n-2}_{i=2}{(b[i]+c[i+1]+n)}$。
4. 情况四：花费为 $\min \limits^{n-2}_{i=2}{(b[i]+d[i+1]+|a[i+1]-a[e[i+1]-1]|+n)}$，且应满足 $e[i]>i+2$。

接下来只需要比较四种情况，取花费最小的即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n;
int a[N],b[N],c[N],d[N],e[N];
int read(){
	int p=1,k=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') p=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
	return p*k;
}
int main(){
	int T=read();
	while(T--){
		memset(a,0,sizeof(a));  //多测清空
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		memset(d,0,sizeof(d));
		memset(e,0,sizeof(e));
		int n=read(),ans=1e9;
		for(int i=1;i<=n;i++){
			a[i]=read();
		}
		for(int i=1;i<=n;i++){   //预处理b、c、d、e四个数组
			b[i]=abs(a[i]-a[1]);
		}
		for(int i=1;i<=n;i++){
			c[i]=abs(a[i]-a[n]);
		}
		d[n]=1e9;
		for(int i=n-1;i>=1;i--){
			if(d[i+1]>c[i]){
				d[i]=c[i];
				e[i]=i;
			}
			else{
				d[i]=d[i+1];
				e[i]=e[i+1];
			}
		}
		ans=min(ans,abs(a[n]-a[1])+n);  //第一种情况
		for(int i=2;i<=n-2;i++){
			ans=min(ans,b[i]+d[i+1]+n+2);  //第二种情况
			ans=min(ans,b[i]+c[i+1]+n);  //第三种情况
			int pos=e[i+1];
			if(pos!=i+1&&pos!=i+2) ans=min(ans,b[i]+d[i+1]+abs(a[i+1]-a[pos-1])+n);  //第四种情况
		}
		printf("%d\n",ans);
	}
	return 0;
}