题解：CF980C Posterized

fish_love_cat · 2025-12-21 15:50:57 · 题解

duel games 遇到的。

本题标签：

博弈论（games）贪心（greedy）*1700

重生之我和乌龟虚空博博弈。

字典序最小，于是直接开贪。

我们尽可能的让遇到的点往小了变。

如果往前跳的过程中遇见了已经分过组的，那检查一下可不可以把这个点也插进去，行的话就合并，不行就独立。

对于每个组我们不把名额分完，从最小的点往后连续到当前点就好，多的名额存下来有需要再放出去。

不这么做的话会挂样例 2，有可能让后面的点变得不优。

实现的话我用的 map，时间复杂度应该是 O(n\log k + k \log k)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int>mp;
map<int,bool>vis;
map<int,int>sy;
signed main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(!vis[x]){
            int j;
            for(j=x;j>=0&&x-j+1<=k;j--){
                if(vis[j])break;
            }
            j++;
            for(int qwq=j;qwq<=x;qwq++){
                vis[qwq]=1;
                if(sy[j-1]+j-1>=x)
                mp[qwq]=mp[j-1];
                else mp[qwq]=j;
            }
            if(sy[j-1]+j-1>=x)sy[x]=sy[j-1]+j-1-x;
            else sy[x]=j+k-1-x;
        }
        cout<<mp[x]<<' ';
    }
    return 0;
}
//「什么都不做的话，那就真的只有请勇者大人将那孩子当作卑兽铲除掉了。
// 要一个小孩子杀掉自己的朋友，站在旁边的大人简直是颜面扫地。
// 能做的事就尽量去做，如果找不到能做的事就自己创造出来。」