2023/02/14 19:32
题意:
给出一个数组,每次操作能把连续的一段数加一或者减一,为最少操作几次能把数组内所有数变成一样,数字有几种情况
思路:
很容易想到差分,但是不知道该怎么进行下去了
我们先看,如果到达目标状态之后,差分数组是怎么样的
可以发现在第二项到第n项查分数组都是0
而第一项恰好是数组的最终值
问题转化成 最少操作多少次可以使得第二项到第n项查分数组都是0
我们可以统计一下差分数组内正数和负数的个数
一共有三种情况
1. 2 <= i, j <= n 这样我们可以同时拉近正数和负数的距离使得更接近0
2. i = 1,2 <= j <= n 这里我们只能改变一个正数或一个负数 这里也改变了首项
3. 2 <= i <= n,j = n + 1 这里同样我们只能改变一个正数或一个负数
由于需要修改次数最小 所以我们需要尽可能完成数量较多的操作1
随后再执行操作2 3 由于我们可以加一也可以减一 所以可以认为2 3操作是等价的
可以出现的数的个数 等价于 差分数组第一个数的个数 也就等价于操作首项的次数
最少操作次数 min(pos, neg) + abs(pos - neg)
可能数字个数 abs(pos - neg) + 1
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> 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;
return 0;
}