[Poetize6] IncDec Sequence(差分)

题意:

给出一数组,已知一次操作可以让一个区间内的数加一或减一,求使得数组内所有元素一致的最少操作数和方案数

解题思路:

1.区间的加减可以用差分来完成,那么使数组内元素一致即可以看成令差分数组内所有元素为零
2.因为一次区间操作可以让差分数组内一个元素+1,一个元素-1或是只取一个元素+1/-1,统计差分数组内所有负值(绝对值)和正值,可以推出最少操作数应该为两个统计值中的最大值,而方案数则为两个统计值的差+1

代码如下:

#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100005
ll a[N],b[N],x,y;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i]; 
        //差分数组
        if(i)b[i] = a[i]-a[i-1];
        //分别统计其中的正值和负值
        if (b[i] > 0)x += b[i];
        else y -= b[i];
    }
    cout << max(x, y) << endl << abs(x - y) + 1;
}