Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-B. One Night At Freddy's（一定要关注数据范围限制）

题目大意

题目描述

一共有 $m$ 个玩偶，初始危险值 $d_1, d_2, \dots, d_m$ 均为 0。

整个过程持续 $\ell$ 秒。在每一秒内，会有一个（且仅有一个）玩偶的危险值增加 1。你可以时刻观察到所有玩偶当前的危险值。

你有 $n$ 次使用手电筒的机会，分别在固定的时间点 $a_1, a_2, \dots, a_n$（$1 \le a_1 < a_2 < \dots < a_n \le \ell$）秒后发生。
每次使用手电筒时，你可以选择恰好一个玩偶，将其危险值重置为 0。每次的选择是互相独立的。

最终的“总危险值”定义为 $\ell$ 秒结束时，所有玩偶危险值的最大值，即 $\max_{1 \le j \le m} d_j$。
你需要求出一个最小的整数 $x$，使得无论每一秒是哪个玩偶的危险值增加，你都能通过合理地使用手电筒，保证最终的总危险值不超过 $x$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, \ell$（$1 \le n, m, \ell \le 2 \cdot 10^5$，$n \le \ell$，$1 \le m \cdot \ell \le 2 \cdot 10^5$），分别代表手电筒使用次数、玩偶数量以及总时长。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_1 < a_2 < \dots < a_n \le \ell$），代表可以使用手电筒的时间点。

保证所有测试用例中 $m \cdot \ell$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，即保证最终总危险值不超过的最小值 $x$。

样例数据

输入

7
1 2 10
10
5 1 32
1 4 9 16 25
2 3 40
13 37
2 2 7
6 7
8 5 60
3 17 20 28 36 44 45 50
6 7 1987
6 7 66 77 666 777
1 1 1
1

输出

5
7
19
1
19
1477
0

样例解释

在第一个测试用例中，有 $2$ 个玩偶，总时长为 $10$ 秒，在第 $10$ 秒后可使用一次手电筒。可以证明 $x=5$ 总是可行的：$10$ 秒后，必定有一个玩偶的危险值至少为 $5$，另一个至多为 $5$。我们对着危险值较大的那个使用手电筒将其清零，那么最终的最大危险值至多为 $5$。可以证明 $5$ 是 $x$ 的最小可能值。

在第二个测试用例中，只有 $1$ 个玩偶，总时长为 $32$ 秒。由于只有 $1$ 个玩偶，它的危险值每秒必定增加 $1$。在最后一次使用手电筒（第 $25$ 秒）时，我们将它的危险值清零。在这之后距离结束还有 $7$ 秒，因此最终危险值必定为 $7$。

在第三个测试用例中，可以证明最小可能的值 $x$ 为 $19$。

思路讲解

就是这个 B，哎，感觉基本上是想到了，但是没关注到一个关键的这个数据范围限制。

一定要关注数据范围限制。

你看到这个，基本就知道简单的贪心和这个二分答案是解决不了的。

其实这道题目，这个思路还是不难的，就是，我们想让我们的每一次操作都在最终的答案中贡献最大，是不是？

然后我们发现，如果说后面还有 N 个手电筒，我们如果给 N 个球加，我们其实对这个最终答案的贡献是 0。

那怎么办？我们可以给 N+1 个球加。

ll cnt=N;
while (SZ(st)>cnt+1) {
    pop();
}
for (int i=1;i<=L;++i) {
    add();
    if (incident[i]) {
        to_zero();
        --cnt;
    }
    while (SZ(st)>cnt+1) {
        pop();
    }
}
ll ans=*st.rbegin();

AC代码

AC

https://codeforces.com/contest/2207/submission/365942294

源代码

/**
 * Problem: B. One Night At Freddy's
 * Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2207/problem/B
 * Created: 2026-03-09 13:31:57
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,M,L;
    cin >> N >> M >> L;
    multiset<ll> st;
    for (int i=1;i<=M;++i) {
        st.insert(0);
    }
    auto add=[&]() {
        if (st.empty()) {
            return;
        }
        ll val=*st.begin();
        st.erase(st.begin());
        st.insert(val+1);
    };
    auto pop=[&]() {
        if (st.empty()) {
            return;
        }
        st.erase(st.begin());
    };
    auto to_zero=[&]() {
        if (st.empty()) {
            return;
        }
        st.erase(prev(st.end()));
        st.insert(0);
    };
    vector<char> incident(L+2);
    for (int i=1;i<=N;++i) {
        ll a;
        cin>>a;
        incident[a]=1;
    }
    ll cnt=N;
    while (SZ(st)>cnt+1) {
        pop();
    }
    for (int i=1;i<=L;++i) {
        add();
        if (incident[i]) {
            to_zero();
            --cnt;
        }
        while (SZ(st)>cnt+1) {
            pop();
        }
    }
    ll ans=*st.rbegin();
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2207/submission/365942294

*/

心路历程（WA，TLE，MLE……）