题解 CF2207B 【One Night At Freddy's】

Leasier · 2026-03-09 16:05:13 · 题解

我方的策略是显然的：每次闪光时选取一个最大的 d_i 并将其置为 0 即可。

有鉴于此，除非 m = 1 或我方已经没有闪光的机会了，对方并不会选择将最大的 d_i 加 1，因为最大者会被我方清零，这相当于做了无用功。

那么对方一定会将最小的 d_{k_0} 加 1，使得各个 d_k “较为平均”，以减小其无用功吗？也不尽然。注意到当 n 较小而 m 很大，我方只有机会对其中 n 个进行闪光，此时对方只需关注其中 n + 1 个，每次将这 n + 1 个中最小的 d_{k_0} 加 1 即可。

推而广之，可得如下贪心算法：

• (1) 对方：在时刻 i，若我方后续还有 j 次闪光机会，则考虑当前前 j + 1 大的 d_k。
• 将这些 d_k 中最小者加 1。
• (2) 我方：在时刻 a_i，选取当前最大的 d_i 并将其置为 0。

用一个 set 模拟即可。时间复杂度为 O(\sum (n + m + l) \log m)。

代码：

#include <iostream>
#include <set>
#include <cstdio>

using namespace std;

int a[200001];
multiset<int> s;

void solve(){
    int n, m, l;
    scanf("%d %d %d", &n, &m, &l);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    s.clear();
    for (int i = 1; i <= m; i++){
        s.insert(0);
    }
    for (int i = 1; i <= n; i++){
        while (s.size() > n - i + 2) s.erase(s.begin());
        for (int j = a[i - 1] + 1; j <= a[i]; j++){
            int mind = *s.begin();
            s.erase(s.begin());
            s.insert(mind + 1);
        }
        s.erase(--s.end());
        s.insert(0);
    }
    cout << *(--s.end()) + (l - a[n]) << endl;
}

int main(){
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++){
        solve();
    }
    return 0;
}