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

· · 题解

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

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

思路：贪心

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

由于一个数加 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