IncDec Sequence

题目描述

给定一个长度为 n(n≤105)的数列a1,a2,…,an每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入描述

第一行一个正整数n。
接下来n行，每行一个整数，第i+1行的整数表示ai。

输出描述

第一行输出最少操作次数。
第二行输出最终能得到多少种结果。

输入样例

4
1
1
2
2

输出样例

1
2

说明

对于100%的数据，n=100000，0 <= ai < 21474836480

思路

每次操作影响的是紧挨着的一段序列，且这一段序列的变化值相等，由此可以将每次变化转变为差分序列的两个值的变化，这样可以将题目化简为，将前缀序列 b1,b2,b3...bn,bn+1，经由一个加一另一个减一的变化使得所有值为b2,b3...bn，在尽量变化次数较少的情况下是将序列b2,b3...bn中的正数减一，负数加一同时进行，这样一次会改变b2,b3...bn序列中的两个数，然后让剩下的正数或负数与b1或b(n+1)进行加一减一的操作。这样最终a序列的所有的值都是b1。易知，设b序列中负数绝对值的和为q，正数和为p，则最少的操作次数为min(p, q) + | p - q |，根据 | p - q |次b1, b(n+1)的选择不同，产生了| p - q |种不同的结果。

示例代码

#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <set>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
const int INF = 0X3F3F3F3F;

const int N = 100005;

long long  a[N];
long long  b[N];

void solve()
{
}

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        b[i] = a[i] - a[i - 1];
    }
    b[n + 1] = 0;

    long long  nega = 0;
    long long posi = 0;

    for (int i = 2; i <= n; i++)
    {
        if (b[i] > 0)
            posi += b[i];
        if (b[i] < 0)
            nega -= b[i];
    }

    cout << max(nega, posi) << endl;
    cout << abs(nega - posi) + 1 << endl;

    return 0;
}