CF1154E

YangXiaopei · 2023-08-02 11:29:30 · 题解

题目传送门

前言：

不懂链表的请先自学再来看此题解或直接跳过。

Solution：

一看到题，就有一个思路：模拟。

但很明显，不管怎样，时间复杂度都为 O(n^2)，无法通过。

我们再来看，每个人只会出一次队，那我们只需再 O(1) 中找到能力最高的人即可，这里可用优先队列模拟，但我这要介绍一种更巧妙的方法。

由于有出队这种操作，我们先想到用链表。

再加上每个人的能力值为 1 到 n 的排列，我们只需把能力值存入链表，用一个标记数组判断是否出过队，再用 while 循环是否为空，每次循环 n 到 1，找到第一个没出队的能力值，再分别左遍历 k，右遍历 k，每次打上标记并把它从链表里删除即可。

最终代码：

#include<bits/stdc++.h>
using namespace std;
int n, k, cnt, pre, l[200010], r[200005], a[200005], f[200005], y[200005], z[200005];
//l、r存链表，f为标记数组，y存下标，z存最终输出。
void link(int x, int y){加入链表操作
    r[x] = y;
    l[y] = x;
    return;
}
void del(int x){删除操作
    link(l[x], r[x]);
    f[x] = 1;
    z[y[x]] = pre;
    return;
}
int HEAD = 0;
int END = 200001;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    int last = 0;
    for(int i = 1; i <= n; i++){//把下标存入链表。
        cin >> a[i];
        link(last, a[i]);
        last = a[i];
        y[a[i]] = i;
    }
    link(a[n], END);
    pre = 1;//用来记录该加入那个队了。
    while(cnt < n){
        for(int i = n; i >= 1; i--){
            if(f[i] == 0){//找到第一个没出队的。
                f[i] = 1;
                for(int j = r[i], m = 1; j != END && m <= k; j = r[j], m++){//右找k个。
                    cnt++;
                    del(j);
                }
                for(int j = l[i], m = 1; j != HEAD && m <= k; j = l[i], m++){//左找k个。
                    cnt++;
                    del(j);
                }
                del(i);
                cnt++;
                break;
            }
        }
        pre++;//当前队伍变换。
    }
    for(int i = 1; i <= n; i++){//最终输出
        z[i] %= 2;
        if(z[i] == 0){
            z[i] = 2;
        }
        cout << z[i];
    }
    return 0;
}

完结撒花