[Poetize6] IncDec Sequence

题目描述

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

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

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

4
1
1
2
2

输出样例#1： 

1
2

说明

对于100%的数据， n<=1e5，0 <= a[i] <= max_inf

 

 

    本来洗完澡风干头发的时候想看一道题再睡觉。。。。然后发现好水啊就现做了23333

    区间+/- 相当于对 差分的 两个位置一个+，一个- ；或者仅仅有一个位置+/-。

    可以发现a[1]和前面的差分可以不用管，只需要让 2~n 和前面的差分都是0就行了，所以我们贪心的算一下差分中，所有负数的和的相反数   和  所有正数的和  中的较大值，就是第一个答案；

    第二问也很简单，，，因为会多出 derta次操作，每次都可以管或者不管1和前面的差分，所以最终序列种数就是 derta+1啦。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100005;
ll n,sum[2],now,pre;

inline int read(){
	int x=0; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

int main(){
	n=read(),pre=read();
	for(int i=2;i<=n;pre=now,i++){
		now=read();
		if(now<=pre) sum[0]+=pre-now;
		else sum[1]+=now-pre;
	}
	
	printf("%lld\n%lld\n",max(sum[0],sum[1]),llabs(sum[0]-sum[1])+1);
	return 0;
}