P4552. IncDec Sequence

发表于 分类于 阅读次数： Waline： 本文字数： 368 阅读时长 ≈ 1 分钟

考点

  • 差分
  • 贪心

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50;
int n;
ll arr[maxn], diff[maxn];

int main() {
  cin >> n;
  ll neg = 0, pos = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
    diff[i] = arr[i] - arr[i - 1];
    if (i > 1) diff[i] < 0 ? neg += -diff[i] : pos += diff[i];
  }
  cout << max(neg, pos) << endl << abs(neg - pos) + 1;
  return 0;
}

思路

根据原数组建立差分数组diff后，题目的要求就变成了：

在差分数组diff中，

除下标1以外，每次在2~n中选两个下标，一个值+1，一个值-1，

求能把除下标1以外的其他位置的值都归0的最小次数。

举个例子，有如下数组：

1 2 4 1 2 3

求出差分数组diff:

1 1 2 -3 1 1

为了让归0的次数最少，显然希望每次都是负数+1，正数-1

两轮后变成了：

1 1 0 -1 1 1

再一轮：

1 1 0 0 1 0

现在场上只剩正数了，继续：

1 0 0 0 2 0

此时如果将diff转回正常数组，得到如下：

1 1 1 1 3 3

在保证最小次数的情况下，也就是只剩2次操作机会，整个序列可以取1或2或3。

综上，设差分数组diff中， 除下标1外的负数绝对值和为neg，除下标1外的正数绝对值和为pos；

最大操作次数等于max(neg, pos)；

序列的可能数等于abs(neg - pos) + 1。