题目描述
小蓝在无聊时随机生成了一个长度为 n 的整数数组,数组中的第 i 个数为ai,他觉得随机生成的数组不太美观,想把它变成回文数组,也是就对于任意i ∈ [1, n] 满足 ai = an−i+1 。小蓝一次操作可以指定相邻的两个数,将它们一起加1 或减 1 ;也可以只指定一个数加 1 或减 1 ,请问他最少需要操作多少次能把这个数组变成回文数组?
输入格式
输入的第一行包含一个正整数 n 。
第二行包含 n 个整数 a1, a2, · · · , an ,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入复制
4
1 2 3 4
样例输出复制
3
提示
【样例说明】
第一次操作将 a1, a2 加 1 ,变为 2, 3, 3, 4 ;后面两次操作将 a1 加 1 ,变为 4, 3, 3, 4 。
【评测用例规模与约定】
对于 20% 的评测用例,1 ≤ n ≤ 10;对于所有评测用例,1 ≤ n ≤ 105 ,−106 ≤ ai ≤ 106 。
1.分析
1.用long long
2.计算 ai 和 an−i+1 的差值,如果相邻 ai 和 ai+1 两个都为正数或负数,就一起加减。然后计算孤立的点 ai 。
2.代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int MAX = 1e5 + 100;LL h[MAX],n,num[MAX],re;int main() {cin >> n;for (int i = 1; i <= n; i++) { //输入cin >> h[i];}for (int i = 1; i <= n / 2; i++) { //计算差值num[i] = h[n - i + 1] - h[i];}for (int i = 1; i < n / 2; i++) {if (num[i] >= 0 && num[i + 1] >= 0) { //都为正数int t = min(num[i], num[i + 1]);num[i] -= t;num[i + 1] -= t;re += t;}else if (num[i] < 0 && num[i + 1] < 0) { //都为负数int t = min(abs(num[i]), abs(num[i + 1]));num[i] += t;num[i + 1] += t;re += t;}if (num[i] > 0) re += num[i]; //计算ai else re -= num[i];num[i] = 0;}if (num[n / 2] > 0) re += num[n / 2]; //中点else re -= num[n / 2];cout << re << endl;return 0;
}