自动搬运

查看原文

来自洛谷，原作者为

	Hyper_zero 喵喵喵|燃尽了

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

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

以下是正文

P10902 [蓝桥杯 2024 省 C] 回文数组题解

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

思路：贪心

题目要求将一个随机数组变成一串回文数，可执行的操作如下：

• 相邻两个数同时加 $1$
• 单个数加 $1$ 或减 $1$

由于一个数加 $1$ 得到回文数和一个数减 $1$ 得到回文数效果一样，我们可以不考虑减 $1$ 的情况。

很显然，相邻两个数同时加 $1$ 要比单个数加 $1$ 或减 $1$ 的步数少，于是我们优先将相邻两个数同时加 $1$。

实现

我们用数组 $b$ 来存放 $a_i$ 需要变化的次数，然后计算相邻两个数可以同时加 $1$ 的次数，最后加上单个数加 $1$ 的次数。

ACcode

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,a[N],b[N],ans;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=(n+1)/2;i++)     //计算 a[i] 需要变化的次数
	{
		if(a[i]<a[n-i+1])           //前一半
			b[i]=a[n-i+1]-a[i];
		else
			b[n-i+1]=a[i]-a[n-i+1]; //后一半
	}
	for(int i=1;i<=n;i++)           //计算步数
	{
		int mn=min(b[i],b[i+1]);    // mn 为相邻两个数可以同时加1的次数
		b[i]-=mn;
		b[i+1]-=mn;
		ans+=mn;                    //加上邻两个数可以同时加1的次数
		ans+=b[i];                  //加上单个数加 1 的次数
	}
	printf("%lld",ans);
}

求过qwq