欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Acwing-100-IncDec序列(差分)

程序员文章站 2022-07-12 17:38:08
...

链接:

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;
}