NC9985D石子游戏_牛客博客

Solution

一遍贪心的差分就够了，从开头往后插有三种情况： $D1$ 代表a[i]处的差分前缀和 $D2 = D1 + d[i + 1]$

$a[i] + D1 = a[i + 1] + D2$

说明两者相等，无需操作。
$a[i] + D1 < a[i + 1] + D2$

a. $i~\%~k~=~0$

说明前方的数都要增加 $a[i + 1] + D2 - a[i] - D1$ ，那么显然 $i \% k == 0$ 。

$ans += \frac{i}{k} * (a[i + 1] + D2 - a[i] - D1)$

b. $i~\%~k~\neq~0$

$NO$
$a[i] + D1 > a[i + 1] + D2$

a. $i + k \le n$

说明后方的k个数都要增加$ $a[i] + D1 - a[i + 1] - D2$

$ans += (a[i] + D1 - a[i + 1] - D2)$

$d[i + 1] += (a[i] + D1 - a[i + 1] - D2)$

$d[i + k + 1] -= (a[i] + D1 - a[i + 1] - D2)$

b. $i + k > n$

$NO$

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

ll n, k, a[N], d[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = 0;
    }
    ll ans = 0, D1 = 0, D2 = 0;
    for (int i = 1; i < n; i++) {
        D1 += d[i];
        D2 = D1 + d[i + 1];
        a[i] += D1;
        if ((a[i] < a[i + 1] + D2 && (i < k || i % k)) || (a[i] > a[i + 1] + D2 && (i + k > n))) {
            ans = -1;
            break;
        }
        if (a[i] < a[i + 1] + D2) {
            ans += i / k * (a[i + 1] + D2 - a[i]);
        } else if (a[i] > a[i + 1] + D2) {
            ans += a[i] - a[i + 1] - D2;
            d[i + 1] += a[i] - a[i + 1] - D2;
            d[i + 1 + k] -= a[i] - a[i + 1] - D2;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}