https://codeforces.com/contest/1154/problem/E

题意：有两个教练来选人，第一个先选。两个人选的策略是：找到还没被选的最大的一个。然后在选择它左边k个和右边k个。他们轮流选直到全部选完。输出他们都被谁选了

C++版本一

题解：链表STL

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
int a[N];

char str;
struct node{
    int val,id;
    bool operator <(const node &S)const{
        return val<S.val;
    }
}e[N];
list<node>st;
list<node>::iterator it[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&e[i].val);
        e[i].id=i;
        st.push_back(e[i]);
        it[i]=--st.end();
    }
    sort(e+1,e+n+1);
    int pos=1;
    for(int i=n;i>=1;i--){
        if(!ans[e[i].id]){
            int now=e[i].id;
            ans[now]=pos;
            list<node>::iterator l=it[now],r=it[now];
            for(int j=1;j<=k;j++){
                if(l!=st.begin())--l;
                if(r!=--st.end())++r;
            }
            ++r;
            while(l!=r) {
                ans[l->id]=pos;
                l=st.erase(l);
            }
            pos=(pos==1)?2:1;
        }

    }
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
    cout<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：定义pre和next数组模拟链表

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
int a[N];
int pre[N],nxt[N];
char str;
struct node{
    int val,id;
    bool operator <(const node &S)const{
        return val<S.val;
    }
}e[N];
//list<node>st;
//list<node>::iterator it[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&e[i].val);
        e[i].id=i;
        //st.push_back(e[i]);
        //it[i]=--st.end();

        pre[i]=i-1;
        nxt[i]=i+1;
    }
    sort(e+1,e+n+1);
    int pos=1;
    for(int i=n;i>=1;i--){
        if(!ans[e[i].id]){
            int now=e[i].id;
            ans[now]=pos;
//            list<node>::iterator l=it[now],r=it[now];
//            for(int j=1;j<=k;j++){
//                if(l!=st.begin())--l;
//                if(r!=--st.end())++r;
//            }
//            ++r;
//            while(l!=r) {
//                ans[l->id]=pos;
//                l=st.erase(l);
//            }
            int l=pre[now];
            int r=nxt[now];
            for(int j=1;j<=k;j++){
                if(l!=0&&!ans[l])
                    ans[l]=pos,l=pre[l];
                else
                    break;
            }
            for(int j=1;j<=k;j++){
                if(r!=0&&!ans[r])
                    ans[r]=pos,r=nxt[r];
                else
                    break;
            }
            //cout<<l<<" "<<r<<endl;
            pre[r]=l;
            nxt[l]=r;
            pos=(pos==1)?2:1;
        }

    }
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
    cout<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}