问题描述
给定一个长度为 n(n≤10^5 ) 的数列 {a_1,a_2,…,a_n}，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行一个正整数n。
接下来n行，每行一个整数，第i+1行的整数表示ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
样例输入
4
1
1
2
2
样例输出
1
2
数据范围与约定
对于100%的数据，n=100000，0<=ai<2147483648
解题思路
考虑差分后的序列
每次对[l,r]进行+1/-1，相当于在差分后的数组上对l进行+1/-1，然后对r+1进行-1/+1
特殊的，如果r=n，那么就相当于对l进行了+1/-1
我们最终的目标是将差分数组变成第一个位置是最终的数字，2~n都是0
那么我们统计差分后的数组的2~n号位置上每个位置上的数
令pos为所有正数的和，neg为所有负数的和的绝对值
那么首先是pos和neg对消 可能会有剩下
剩下的有两种选择：自己消掉或者与1号位置对消
故第一问答案为max(pos,neg) 第二问答案为abs(pos-neg)+1
#include<bits/stdc++.h>
using namespace std;
int n,a[200000];
int main()
{
scanf("%d",&n);
long long pos=0,neg=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
int p=a[i]-a[i-1];
if(i==1)continue;
if(p>0)pos+=p;
else neg+=p;
}
neg*=-1;
long long ans1=max(pos,neg);
long long ans2=abs(pos-neg)+1;
printf("%lld\n%lld",ans1,ans2);
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103170.html
