题解 CF2207B One Night At Freddy's

· · 题解

题解 CF2207B One Night At Freddy's

其他题（几天后完工）

自评：橙\~黄（本题）黄（Bonus）。

挺久没见过《玩具熊的五夜后宫》相关了。想当年各 scratch 网站上面还有一车人在复刻来着。

题意

给定 m 个玩具熊，第 i 个的危险度是 d_i，初始 d_i=0。整个晚上共 l 秒，每秒会有恰好一个玩具熊的危险度增加 1。你有 n 次打闪的机会，第 i 次在第 a_i 秒结束后（即玩具熊已经完成加强）可以选一个玩具熊闪，被闪到的这个玩具熊的危险度变为 0。求整个晚上结束后危险值最大的玩具熊危险值至少为多少。

数据范围：多测，t\le 10^4,n\le l\le 2\times 10^5,m\le 2\times 10^5,1\le a_1<\dots<a_n\le l,\sum ml\le 2\times10^5。

Bonus（By 我自己）：去掉最后一个限制。

做法

玩家的策略是很显然的：既然要最小化最大值，那就每次对着最大的干。

于是对面的策略也是很显然的：尽可能平均地点各个熊来避免亏损。

但是只是这么做肯定有问题，比如我最后一次闪完了再平均点就没用了，不如对着一个点。

于是其实对面准确的策略应该是，如果玩家当前剩 k 个闪，那对面只需要平均点危险值最大的 k+1 个熊就可以了，因为我最多闪掉 k 个，还能给剩一个。

于是拿个 multiset 维护一下即可。单组复杂度 O(l\log m)。当然题目里限制了 ml 的范围所以也可以暴力，不过 STL 不比暴力好写？

小技巧是你开局就只放 \min\{n+1,m\} 个，然后每次闪完判断是否还要留着被闪掉的这个就行。

另外感觉应该可以有更大的 Bonus（比如 l 大一点啥的），但没想出来。有想到的大手子浇浇。

//Please ignore those headfiles.I write them just because
//DEV-C++ won't support completion if i use <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<queue>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
#define LL __int128
#define ui unsigned int
using namespace std;
ll T,n,m,l,a[200010],b[200010];
multiset<ll> s;
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>l;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        s.clear();
        for(int i=0;i<min(n+1,m);i++){
            s.insert(0);
        }
        ll pos=0;
        multiset<ll>::iterator it;
        for(int i=0;i<n;i++){
            while(pos<a[i]){
                pos++;
                s.insert((*s.begin())+1);
                s.erase(s.begin());
            }
            it=s.end();
            it--;
            s.erase(it);
            if(n-i>s.size()){
                s.insert(0);
            }
        }
        it=s.end();
        it--;
        cout<<(*it)+(l-pos)<<endl;
    }
    return 0;
}