蓝桥杯 回文数组

问题描述

小蓝在无聊时随机生成了一个长度为 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

样例输出

3

---

样例说明

第一次操作将 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

解题思路

贪心算法

每次遍历只要有相邻的数同时大于或者同时小于对应回文数，则对两个数同时操作。

没有任何一对这样的数的时候，再单独操作。