链接:
https://www.acwing.com/problem/content/102/
题意:
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
思路:
就是将查分数组除了第一位都置为0, 的操作步数,因为每次只能加1或减一.可以优先配对一正以偶负,再对剩余的值进行处理.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
int a[MAXN], Sub[MAXN];
int n;
int main()
{
LL ne = 0, po = 0;
scanf("%d", &n);
for (int i = 1;i <= n;i++)
{
scanf("%d", &a[i]);
Sub[i] = a[i]-a[i-1];
if (i <= 1)
continue;
if (Sub[i] > 0)
po += Sub[i];
else
ne += abs(Sub[i]);
}
LL oth = abs(po-ne);
printf("%lld\n%lld\n", max(ne, po), oth+1);
return 0;
}