Acwing-100-IncDec序列(差分)

链接:

https://www.acwing.com/problem/content/102/

题意:

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

思路:

就是将查分数组除了第一位都置为0, 的操作步数,因为每次只能加1或减一.可以优先配对一正以偶负,再对剩余的值进行处理.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

int a[MAXN], Sub[MAXN];

int n;

int main()

{

    LL ne = 0, po = 0;

    scanf("%d", &n);

    for (int i = 1;i <= n;i++)

    {

        scanf("%d", &a[i]);

        Sub[i] = a[i]-a[i-1];

        if (i <= 1)

            continue;

        if (Sub[i] > 0)

            po += Sub[i];

        else

            ne += abs(Sub[i]);

    }

    LL oth = abs(po-ne);

    printf("%lld\n%lld\n", max(ne, po), oth+1);

    return 0;

}