p10902回文数组

类型：贪心

思路：

这个题要用对称的思想来看，左边加一和右边减一其实是一样的，所以我们只看一边，记录左边要变成右边需要几(b[N]的作用)，然后遍历一次b数组，如果b[i]和b[i + 1]需要的性质是一样的(都+或都-)那么可以省去b[i+1]一部分步数，从而得到最小步数

代码：

#include <iostream>
#include <cmath>
#define int long lnog
using namespace std;
const int N = 1e6 + 11;
int a[N],b[N >> 1];
int sum,cnt;
signed main(){
    int n;
    cin >> n;
    int j = 0;
    for (int i = 0;i < n;i ++) {
        cin >> a[i];
    }
    for (int i = 0;i < n / 2;i ++){ //n == 4
        b[j ++] = a[i] - a[n - i - 1];
    }
    int len = j;
    for (int i = 0;i < len;i ++){
        cnt += abs(b[i]);
        if (b[i] > 0 && b[i + 1] > 0){
            b[i + 1] -= min(b[i],b[i + 1]);
        }
        if (b[i] < 0 && b[i + 1] < 0){
            b[i + 1] -= max(b[i],b[i + 1]);
        }

    }
    cout << cnt;
    return 0;
}