题目链接:传送门
将序列转化成差分数列
那么题目就变成了对一个数组可进行三种操作
对两个元素一个加一一个减一或对一个元素加一或对一个元素减一
其实后面两种操作实质是对一个元素和队首或队尾进行操作
求最少的操作数使数组所有元素变成,贪心即可
累计所有正数和,
累计所有负数和
抵消掉一部分,
处理剩下的
就是最小的操作数
最终的序列有种
因为还剩下的种操作是对队尾或队首的操作
队尾或队首就会影响这个数列的值,所以最多加那么多次,最少一种
#include <bits/stdc++.h>
using namespace std;
int n, a[100010]; long long f1, f2;
int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 2; i <= n; i++) {int x = a[i] - a[i - 1]; x > 0 ? f1 += x : f2 -= x;}
cout << min(f1, f2) + abs(f1 - f2) << endl << abs(f1 - f2) + 1 << endl;
}