【bzoj3043】IncDec Sequence

2014年11月23日1,2710

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

题解

设差分序列为d

要使得整个序列相同,即d[i]=0(2≤i≤n)

题目相当于允许将d序列某个值+1,某个值-1

设∑ d[i] (2≤i≤n&&d[i]≥0) = a

∑ d[i] (2≤i≤n&&d[i]≤0) = b

显然第一问答案是max(a,b)。。。

将负数和正数配对消去后。。。剩下的abs(a-b)次操作可以配对给d[n+1]/d[1]

所以d[1]最终取值abs(a,b)+1种