题目描述

Description

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

Input

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

Output

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

Sample Input

4
1
1
2
2

Sample Output

1
2

HINT

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

题目分析

一道好题= =
首先将原数列差分 得到差分序列，那么使得数列中的数都一样的话 就是使(2~n)的差分序列都为0
因为区间加/减在差分序列上相当于 左端点+/-1 (右端点+1)-/+1 那么我们先将正数和负数抵消 剩下的再和第一个值抵消 所以最多次数=max(abs(min(-)),abs(max(+)));
因为可以改大可以改小 所以可能的值就是 剩余的值+1

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long a[1000010];
long long sum,sum2;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=n;i>=2;i--) a[i]=a[i]-a[i-1];
    for(int i=2;i<=n;i++) 
        if(a[i]>=0) sum+=a[i];
        else sum2+=a[i];
    printf("%lld\n%lld",max(-sum2,sum),abs(sum+sum2)+1); 
    return 0;
}