CF1154E题解

Nuyoah_awa · 2023-02-28 18:30:28 · 题解

题目分析

首先想到暴力，找到一个能力最大的人，将他左边 k 个没被选的和右边 k 个没被选的将其归队。

总的时间效率是 O(n ^ 2) 的。

考虑到每回在找旁边 k 个人时有很多是已经被选过的，所以可以使用双向链表，将所有被选过的从链表中删掉，在剩下的人里面向两边找 k 个。

楼上大佬使用栈实现 O(1) 查找最大，我使用的是下标排序法：一个数组，a_i 表示第 i 大的数的下标（如下 node2），顺序遍历。

由于每个点都只被归一次队，所以最终的时间复杂度是 O(n)的。

code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
struct node1{
    int val, ans, left, right;
}p[1000000];
struct node2{
    int val, ans, pos;
}q[1000000];
bool cmp(node2 x, node2 y)
{
    return x.val > y.val;
}
int main(int argc, char** argv)
{
    int n, k, i, j, s = 1;
    scanf("%d %d", &n, &k);
    p[0].left = n;
    p[0].right = 1;
    for(i = 1;i <= n;i++)
    {
        scanf("%d", &p[i].val);
        q[i].val = p[i].val;
        q[i].pos = i;
        p[i].ans = 0;
        p[i].left = i - 1;
        p[i].right = i + 1;
    }
    p[n].right = n + 1;
    sort(q + 1, q + n + 1, cmp);
    for(i = 1;i <= n;i++)
    {
        if(p[q[i].pos].ans != 0)
            continue;
        p[q[i].pos].ans = s;
        int now = q[i].pos;
        for(j = 1;j <= k;j++)
        {
            now = p[now].right;
            if(now == n + 1)
                break;
            p[now].ans = s;
            p[p[now].left].right = p[now].right;
            p[p[now].right].left = p[now].left;
        }
        now = q[i].pos;
        for(j = 1;j <= k;j++)
        {
            now = p[now].left;
            if(now == 0)
                break;
            p[now].ans = s;
            p[p[now].left].right = p[now].right;
            p[p[now].right].left = p[now].left;
        }
        now = q[i].pos;
        p[p[now].left].right = p[now].right;
        p[p[now].right].left = p[now].left;
        s = 3 - s;
    }
    for(i = 1;i <= n;i++)
        cout << p[i].ans;
    return 0;
}