2021牛客寒假算法基础集训营5 石子游戏（差分、思维）

Description

图片说明

Solution

前置知识: 差分
不懂差分的同学可以百度先进行学习。学会差分能够 $O(1)$ 实现题目中的相邻 $k$ 个石子堆数目加 $1$ ，有助于我们进一步处理。
首先思考，对于每一个石子数量，如果当前的数量不是 $n$ 堆石头里面最大值 $maxz$ ，那么它一定要进行差分操作，差分到变成 $maxz$
但是考虑到这样后面的石头可能也会因此增加，所以 $maxz$ 会不断改变，需要我们去维护。
此外，考虑以下数据 $k = 3, a = [1, 0, 0, 1]$ 一开始我们不会操作 $1$ , 但是由于后面 $maxz$ 的改变，第一个 $1$ 现在已经不是 $maxz$ ，所以在从左到右做完一遍后，还需要在 $[1, n - k + 1]$ 里继续检查是否需要差分。
至于什么时候输出 $-1$ ? 如果 $i \geq n - k, a[i] \neq maxz$ 此时无法操作，肯定输出 $-1$ 了。
此外，最后从头到尾检验是不是所有数字相同，如果不是就输出 $-1$ ，否则就输出差分次数即可。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
ll a[N], t[N], tmp[N];
void solve() {
  int n, k; cin >> n >> k;
  ll maxz = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    t[i] = a[i] - a[i - 1];
    maxz = max(maxz, a[i]);
  }
  ll sum = 0;
  int ok = 1;
  ll ans = 0;
  for (int i = 1; i <= n; i++) { // 第一遍差分
    sum += t[i];
    maxz = max(maxz, sum);
    if (i <= n - k + 1) {
      if (sum < maxz) {
        t[i] += maxz - sum;
        t[i + k] -= maxz - sum;
        ans += maxz - sum;
        sum += maxz - sum;
      }
    } else {
      if (sum < maxz) { // 无法差分 不为maxz
        ok = 0;
      }
    }
  }
  sum = 0;
  for (int i = 1; i <= n; i++) { // 第二遍差分
    sum += t[i];
    maxz = max(maxz, sum);
    if (i <= n - k + 1) {
      if (sum < maxz) {
        t[i] += maxz - sum;
        t[i + k] -= maxz - sum;
        ans += maxz - sum;
        sum += maxz - sum;
      }
    } else {
      if (sum < maxz) { // 无法差分 不为maxz
        ok = 0;
      }
    }
  }
  sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += t[i];
    if (sum != maxz) { // 不为maxz
      ok = 0;
      break;
    }
  }
  if (!ok) {
    cout << -1 << '\n';
  } else {
    cout << ans << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}
/*
1
6 3
6 5 4 3 4 5
ans : 3

1
4 3
1 0 0 1
ans : 2

1
7 3
4 2 2 1 1 1 2
ans : 5
*/