首页 > 代码库 > BZOJ 3043: IncDec Sequence
BZOJ 3043: IncDec Sequence
3043: IncDec Sequence
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 578 Solved: 325
[Submit][Status][Discuss]
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
Source
Poetize6
分析:
差分的思想...
考虑在原来的数列中对一个区间$[l,r]+1$,那么就相当于在差分之后的数列上对$l+1$对$r+1$进行$-1$操作,所以我们可以统计出差分之后的数列中的正数和负数,正数和负数可以相消,剩下的数字有两种选择,一种是自己消...一种是和第一个数消...所以最少的次数位$max(positive,negative)$,数列个数就是$abs(positive-negative)+1$...
代码:
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>//by NeighThornusing namespace std;const int maxn=100000+5;int n,a[maxn];long long pos,neg;signed main(void){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++) if(a[i]<a[i+1]) pos+=a[i+1]-a[i]; else if(a[i]>a[i+1]) neg+=a[i]-a[i+1]; printf("%lld\n%lld\n",max(pos,neg),abs(pos-neg)+1); return 0;}
By NeighThorn
BZOJ 3043: IncDec Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。