3043: IncDec Sequence
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 589 Solved: 332Description
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。Input
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
。Output
第一行输出最少操作次数
第二行输出最终能得到多少种结果Sample Input
4
1
1
2
2Sample Output
1
2HINT
对于100%的数据，n=100000，0<=ai<2147483648
Source
【分析】
脑子真的是越来越屎了。。
膜了一下wohenshuai。。
差分，就是-1和+1，-1，+1操作，要全部变成0，显然第一问是max(正数和，负数和)[绝对值]
第二问是正值和与负值和[绝对值]差值+1，因为剩下那个数自己消的情况下也可以和1一起消。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define Maxn 100010 LL a[Maxn],ss[Maxn]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int i=;i<=n;i++) ss[i]=a[i]-a[i-];
LL a1=,a2=;
for(int i=;i<=n;i++) if(ss[i]>) a1+=ss[i];
else a2+=-ss[i];
printf("%lld\n%lld\n",max(a1,a2),abs(a1-a2)+);
return ;
}
2017-04-11 21:12:14