首页 > 代码库 > IncDec Sequence（codevs 2098）
IncDec Sequence（codevs 2098）
题目描述 Description
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。
输入描述 Input Description
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
输出描述 Output Description
第一行输出最少操作次数
第二行输出最终能得到多少种结果
样例输入 Sample Input
4
1
1
2
2
样例输出 Sample Output
1
2
数据范围及提示 Data Size & Hint
对于100%的数据，n=100000，0<=ai<2147483648。
/* 典型的差分题目 先做一个差分序列b，接下来就是怎么把除了b1之外的所有数都变成0，因为可以进行区间修改，那么对于序列b来说就是一个数加1的同时一个数减1，或一个数加1，或一个数减1。因为要求步数最少，所以要尽可能把加1用在负数上，把减1用在正数上，剩下的只有正数或负数时再单独加1或减1。至于方案数，取决于b1，那么我们要在不影响步数的情况下修改b1，那么只能把单独加1或减1换成修改b1和原来那个数。 */#include<cstdio>#include<iostream>#define M 100010#define ll long longusing namespace std;ll a[M],b[M];int n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]-a[i-1]; } ll tot1=0,tot2=0; for(int i=2;i<=n;i++) if(b[i]>0)tot1+=b[i]; else tot2-=b[i]; cout<<max(tot1,tot2)<<endl<<max(tot1-tot2,tot2-tot1)+1; return 0;}
IncDec Sequence（codevs 2098）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。