给定一个长度为
的数列
,每次可以选择一个区间
,使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
第一行输入正整数
。
接下来
行,每行输入一个整数,第
行的整数代表
。
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
,
4
1
1
2
2
1
2
/*
假设序列为:
9 13 11 14
则差分序列为:
b1 b2 b3 b4 b5
9 4 -2 3 0
我们让 b2, b3, b4 都为 0 就行了
但是对差分的操作必须是成对的,即 bi +1 了,必须有 bj -1
因此本题思路:
- 第一步,找到 b2 到 bn 中有多少个正数,其和是多少:pos
- 第二步,找到 b2 到 bn 中有多少个负数,其和的绝对值是多少:neg
- pos 和 neg 中取小的值,即可以进行多少对 (bi +1, bj -1) 的操作
一下把两个数往0接近
- 然后加上 abs(pos - neg) 即还差多少是配不到对的,需要配合 (bi +1, b1 -1) 这种操作
- 对于 abs(pos - neg) ,我可以与 0 配合,也可以与 bn 配合
因此一共有 abs(pos - neg) + 1 种选法
(假设 abs(pos - neg) == 3 ,则有 (0,3) (1,2) (2,1) (3, 0) 种
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for (int i = n; i >= 1; -- i) a[i] -= a[i - 1];
LL pos = 0, neg = 0;
for (int i = 2; i <= n; ++ i)
{
if (a[i] > 0) pos += a[i];
else neg -= a[i];
}
cout << min(pos, neg) + abs(pos - neg) << endl;
cout << abs(pos - neg) + 1 << endl;
}