[蓝桥杯 2024 省 C] 回文数组
题目名字 [蓝桥杯 2024 省 C] 回文数组
题目链接
题意
给n个数字，用最少的次数，通过同时两个数字或单个数字加一或减一使给的这一串数字变成回文数
思路
- 字眼最少其实就需要判断出这个大概就是贪心了，不过很可惜比赛的时候就只想到了回文，想破了脑袋。。。
- 然后呢我们就需要用到回文的知识点啦，一般是取这串数字的一半来加减的，那么就可以用到一个数组来存储第i个和第n-+1个的差值，有可能会遇到产生负数的情况，所以需要用abs了
- 然后就是分情况讨论了，当第i个和第i+1个为正数的时候，就需要取两个数中小的那个数用b[i+1]数组给剪掉，因为sum在循环开始的时候已经加上了b[i]次了
坑点
- 不算坑点但是属于是完全有这个知识点，min和max的使用，是在Sstl库函数里面的，以及abs函数的使用
- x
- x
算法一：XX+XX
时间复杂度
$
实现步骤
- x
- x
- x
代码
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=1e5+10;
long long n,a[N],b[N];
int main(){
long long int sum=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
b[i]=a[i]-a[n-i+1];
}
for(int i=1;i<=n/2;i++){
sum+=abs(b[i]);
if(b[i]<0&&b[i+1]<0){
b[i+1]-=max(b[i],b[i+1]);
}
if(b[i]>0&&b[i+1]>0){
b[i+1]-=min(b[i],b[i+1]);
}
}
cout<<sum;
return 0;
}