算法题：IncDec Sequence

问题描述

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

输入格式

第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示a~i~。

输出格式

第一行输出最少操作次数

第二行输出最终能得到多少种结果

样例

输入

4
1
1
2
2

输出

1
2

数据范围

对于100%的数据，n=100000，0≤ai<2147483648。

解决方案

思路

差分

代码

#include <iostream>

using namespace std;
long long arr[100005];
long long d[100005];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        d[i] = arr[i] - arr[i - 1];
    }

    long long p = 0, q = 0;
    for (int i = 2; i <= n; i++) {
        if (d[i] > 0) p += d[i];
        else q -= d[i];
    }
    cout << max(p, q) << endl;
    cout << abs(p - q) + 1;
    return 0;
}