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