当前位置：首页 > article >正文

蓝桥杯回文数组

article 2025/3/29 21:18:08

问题描述

小蓝在无聊时随机生成了一个长度为 n 的整数数组，数组中的第 i 个数为 a_i，他觉得随机生成的数组不太美观，想把它变成回文数组，也就是对于任意 i ∈ [1, n] 满足：

a_i = a_(n-i+1)

小蓝一次操作可以指定相邻的两个数，将它们一起加 1 或减 1；也可以只指定一个数加 1 或减 1。请问他最少需要操作多少次才能把这个数组变成回文数组？

输入格式

输入的第一行包含一个正整数 n，表示数组的长度。
第二行包含 n 个整数 a_1, a_2, ..., a_n，相邻整数之间使用一个空格分隔。

输出格式

输出一行，包含一个整数，表示最少需要的操作次数。

样例输入

4
1 2 3 4

样例输出

样例说明

第一次操作将 a_1, a_2 加 1，变为 2, 3, 3, 4；

后面两次操作将 a_1 加 1，变为 4, 3, 3, 4。

评测用例规模与约定

对于 20% 的评测用例，1 ≤ n ≤ 10；
对于所有评测用例，1 ≤ n ≤ 10^5，-10^6 ≤ a_i ≤ 10^6。

c++代码

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

typedef long long ll;

ll n;
vector<ll> arr;
vector<ll> tar;

int main() {
    scanf("%lld", &n);
    ll k = n / 2, ans = 0;
    arr = vector<ll>(k);
    tar = vector<ll>(k);
    for (ll i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
    }
    if (n % 2 != 0) scanf("%d", &n);
    for (ll i = 0; i < k; i++) {
        scanf("%d", &tar[k - i - 1]);
    }
    while(true) {
        bool key = false;
        for (ll i = 0; i < k - 1; i++) {
            if (arr[i] > tar[i] && arr[i + 1] > tar[i + 1]) {
                key = true;
                int w = min(arr[i] - tar[i], arr[i + 1] - tar[i + 1]);
                arr[i] -= w;
                arr[i + 1] -= w;
                ans += w;
            }
            else if (arr[i] < tar[i] && arr[i + 1] < tar[i + 1]) {
                key = true;
                int w = min(tar[i] - arr[i], tar[i + 1] - arr[i + 1]);
                arr[i] += w;
                arr[i + 1] += w;
                ans += w;
            }
        }
        if (!key) {
            for (ll i = 0; i < k; i++) {
                ans += abs(arr[i] - tar[i]);
            }
            break;
        }
    }
    printf("%lld", ans);
    return 0;
}//by wqs