【BZOJ3043】IncDec Sequence
Description
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。
Input
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
。
Output
第一行输出最少操作次数
第二行输出最终能得到多少种结果
Sample Input
4
1
1
2
2
1
1
2
2
Sample Output
1
2
2
HINT
对于100%的数据，n=100000，0<=ai<2147483648
题解：直接说思路，将原序列差分，这样的话区间加1就变成了在左端点+1，右端点-1。
然后乱搞即可。
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
typedef long long ll;
int n;
ll s1,s2;
int v[100010];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i;
for(i=1;i<=n;i++)
{
v[i]=rd();
if(i>1)
{
if(v[i]>v[i-1]) s1+=v[i]-v[i-1];
else s2+=v[i-1]-v[i];
}
}
if(s1>s2) swap(s1,s2);
printf("%lld\n%lld",s2,s2-s1+1);
return 0;
}