CF1154E题解

ztntonny · 2023-02-28 15:03:28 · 题解

思路

从队列中拿出人，第一眼链表加模拟。

1. 写一个链表，每一个元素包含这个人的能力值、这个人前面的人是谁以及后面是谁，以及一个表示该人还是否在队列中的布尔。
2. 打一个结构体数组，每一个元素包含这个人的能力值、这个人初始的位置，排序后找到能力值排名以及对应的人。
3. 从大到小遍历能力值，每一次判断该能力值所对应人是否还在队列中，如果是，则用链表向两边延伸，左右各 k 个都标记在输出数组中、状态变为不在队列中。在都遍历完后，将向右向左的第 k+1 个的两个人连接在一起。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct T
{
    ll bef , aft , ability;
    bool state;
}t[1000005];

struct A
{
    ll abi , pos;
}a[1000005];

bool cmp( A x , A y )
{
    return x.abi > y.abi;
}

ll k , n , st[1000005] , srt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL) , cout.tie(NULL);
    cin >> n >> k;
    for ( int i = 0; i < 1000005; i++ ) t[i].bef = i - 1 , t[i].aft = i + 1 , t[i].state = false;
    for ( int i = 1; i <= n; i++ )  cin >> t[i].ability , t[i].state = true , a[i].abi = t[i].ability , a[i].pos = i;
    sort( a + 1 , a + n + 1 , cmp );
    for ( int i = 1; i <= n; i++ )
    {
        if ( t[a[i].pos].state )
        {
            if ( srt == 1 ) srt = 2;
            else    srt = 1;
            st[a[i].pos] = srt;
            ll p = t[a[i].pos].bef;
            for ( int i = 1; i <= k && p >= 1; i++ )    st[p] = srt , t[p].state = false , p = t[p].bef;
            ll l = p;
            p = t[a[i].pos].aft;
            for ( int i = 1; i <= k && p <= n; i++ )    st[p] = srt , t[p].state = false , p = t[p].aft;
            ll r = p;
            t[l].aft = r , t[r].bef = l;
        }
    }
    for ( int i = 1; i <= n; i++ )  cout << st[i];
    return 0;
}