题目来源：
https://codeforces.com/contest/1154/problem/E
代码来自:fzchen.top
There are nn students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.
The ii-th student has integer programming skill aiai. All programming skills are distinct and between 11 and nn, inclusive.
Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and kk closest students to the left of him and kk closest students to the right of him (if there are less than kk students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).
Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.
Input
The first line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of students and the value determining the range of chosen students during each move, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiaiis the programming skill of the ii-th student. It is guaranteed that all programming skills are distinct.
Output
Print a string of nn characters; ii-th character should be 1 if ii-th student joins the first team, or 2 otherwise.
Examples
Input
5 2
2 4 5 3 1 Output
11111
Input
5 1
2 1 3 5 4 Output
22111
Input
7 1
7 2 1 3 5 4 6 Output
1121122
Input
5 1
2 4 5 3 1 Output
21112
Note
In the first example the first coach chooses the student on a position 33, and the row becomes empty (all students join the first team).
In the second example the first coach chooses the student on position 44, and the row becomes [2,1][2,1] (students with programming skills [3,4,5][3,4,5] join the first team). Then the second coach chooses the student on position 11, and the row becomes empty (and students with programming skills [1,2][1,2] join the second team).
In the third example the first coach chooses the student on position 11, and the row becomes [1,3,5,4,6][1,3,5,4,6] (students with programming skills [2,7][2,7] join the first team). Then the second coach chooses the student on position 55, and the row becomes [1,3,5][1,3,5](students with programming skills [4,6][4,6] join the second team). Then the first coach chooses the student on position 33, and the row becomes [1][1] (students with programming skills [3,5][3,5] join the first team). And then the second coach chooses the remaining student (and the student with programming skill 11 joins the second team).
In the fourth example the first coach chooses the student on position 33, and the row becomes [2,1][2,1] (students with programming skills [3,4,5][3,4,5] join the first team). Then the second coach chooses the student on position 11, and the row becomes empty (and students with programming skills [1,2][1,2] join the second team).
题意：给出一排人，以1~n的一个排列作为他们的权值，2教练和1教练每次从中选择权值最大的一个人和他左边k个人和右边k个人，求最后每个人是被1选还是被2选。(1≤k≤n≤2∗10^5,1≤ai≤n1≤k≤n≤2∗10^5,1≤ai≤n，保证技巧值唯一)
思路：由于存在出列的操作，我们需要将数据存储在链表上。（方便删除被选中的结点）
再弄一个pair数组，存储数据和结点指针。对数组排序可以快速得到当前的最大值并找到该结点。
最后按照题目模拟过程删除结点记录1或者2最后输出即可。
参考代码：
#include<bits/stdc++.h>
using namespace std;
int n, k;
typedef struct node* pointer;
struct node
{
int data;
int id;
pointer sub;
pointer pre;
};
typedef pointer Linklist;
pair<int, pointer>mmax[200010];
int ans[200010];
bool cmp(pair<int, pointer>a, pair<int, pointer>b)
{
return a.first > b.first;
}
void delnode(pointer p)
{
pointer pre = p->pre;
pointer sub = p->sub;
if(pre!=NULL)
pre->sub = sub;
if(sub!=NULL)
sub->pre = pre;
//标记该结点已被删除
p->data = -1;
}
int main()
{
cin >> n >> k;
Linklist l = new node;
//头结点保存的是链表结点个数
l->data = n;
l->pre = l->sub = NULL;
pointer p = l;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
pointer xxx = new node;
mmax[i] = make_pair(x, xxx);
xxx->data = x;
xxx->id = i;
xxx->sub = p->sub;
xxx->pre = p;
p->sub = xxx;
p = p->sub;
}
sort(mmax, mmax + n, cmp);
//now为当前选择的人 0表示第一个人 1表示第二个人
int now = 0;
for (int i = 0; i < n; i++)
{
pointer ppp = mmax[i].second;
if (ppp->data == -1)
continue;
//若未被选
if (ans[ppp->id] == 0)
{
ans[ppp->id] = now + 1;
pointer pre = ppp->pre;
pointer sub = ppp->sub;
delnode(ppp);
l->data--;
for (int p = k; p > 0 && pre != NULL && pre != l; p--)
{
ans[pre->id] = now + 1;
//保存当前结点的前驱后删除结点
pointer q = pre->pre;
delnode(pre);
pre = q;
l->data--;
}
for (int p = k; p > 0 && sub != NULL; p--)
{
ans[sub->id] = now + 1;
//保存当前结点的后继后删除结点
pointer q = sub->sub;
delnode(sub);
sub = q;
l->data--;
}
now = 1 - now;
}
//若数组元素个数为0
if (l->data == 0)
break;
}
for (int i = 0; i < n; i++)
cout << ans[i];
return 0;
} 另外一个大佬给出的代码：线段树+路径压缩：
思路：线段树维护最大权值和权值最大的人的序号，选出的人权值修改成0， 用数组 l[i] 和 r[i] 记录每个人左边的人和右边的人。最终时间复杂度O（nlogn）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx = 2e5 + 5;
int a[maxx];
int v[maxx];
int n, k;
struct SegmentTree
{
int l, r, mx, loc;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define mx(x) tree[x].mx
#define loc(x) tree[x].loc
}tree[maxx<<2];
const int INF = 1e9;
void buildTree(int p, int l, int r)
{
l(p) = l, r(p) = r;
if(l == r)
{
mx(p) = a[l];
loc(p) = l;
return;
}
int mid = l + r >> 1;
buildTree(p<<1, l, mid);
buildTree(p<<1|1, mid+1, r);
if(mx(p<<1) >= mx(p<<1|1))
{
mx(p) = mx(p<<1);
loc(p) = loc(p<<1);
}
else
{
mx(p) = mx(p<<1|1);
loc(p) = loc(p<<1|1);
}
}
void change(int p, int x, int v)
{
if(x == 0 || x == n+1)
return;
if(l(p) == r(p))
{
mx(p) = v;
loc(p) = x;
return;
}
int mid = l(p) + r(p) >> 1;
if(x <= mid)
{
change(p<<1, x, v);
}
else change(p<<1|1, x, v);
if(mx(p<<1) >= mx(p<<1|1))
{
mx(p) = mx(p<<1);
loc(p) = loc(p<<1);
}
else
{
mx(p) = mx(p<<1|1);
loc(p) = loc(p<<1|1);
}
}
pair<int, int> askMaxLoc(int p, int l, int r)
{
if(l <= l(p) && r >= r(p))
return make_pair(mx(p), loc(p));
int mid = l(p) + r(p) >> 1;
pair<int, int>res = make_pair(0, 0);
if(l <= mid)
{
pair<int, int> rem = askMaxLoc(p<<1, l, r);
if(rem.first > res.first)
{
res = rem;
}
}
if(r > mid)
{
pair<int, int> rem = askMaxLoc(p<<1|1, l, r);
if(rem.first > res.first)
{
res = rem;
}
}
return res;
}
int l[maxx], r[maxx];
int main()
{
memset(v, -1, sizeof(v));
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i)
l[i] = i-1, r[i] = i+1;
l[0] = 0, r[n+1] = n+1;
buildTree(1, 1, n);
int ok = 0;
int master = 1;
while(ok < n)
{
int loc = askMaxLoc(1, 1, n).second;
change(1, loc, 0);
if(~v[loc])
break;
else
v[loc] = master;
int ll = loc, rr = loc;
for(int i = 0; i < k; ++i)
{
int reml = ll, remr = rr;
ll = l[ll], rr = r[rr];
if(v[ll] == -1)
v[ll] = master, change(1, ll, 0), ok++, l[reml] = l[ll];
if(v[rr] == -1)
v[rr] = master, change(1, rr, 0), ok++, r[remr] = r[ll];
}
r[l[ll]] = r[rr], l[r[rr]] = l[ll];
master ^= 1;
}
for(int i = 1; i <= n; ++i)
if(v[i])
putchar('1');
else
putchar('2');
return 0;
} 最近又看见的一个大佬写的set+并查集：
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int a[200005];
int rfather[200005];
int lfather[200005];
int mp[200005];
int ans[200005];
int rfin(int x)//向右移动到右边界 右边第一个未被选择的
{
if(rfather[x]==x) return x;
return rfather[x]=rfin(rfather[x]);
}
int lfin(int x)//向左移动到左边界 左边第一个未被选择的
{
if(lfather[x]==x) return x;
return lfather[x]=lfin(lfather[x]);
}
set<int,greater<int> > st;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
st.insert(a[i]);
mp[a[i]]=i;
}
for(int i=0;i<=1+n;i++)
{
rfather[i]=i;
lfather[i]=i;
}
int cnt=0;//已经完成的个数
int x=0;//对x取余来 实现记录哪一队
while(cnt<=n)
{
x++;
int tmp;
int pos;
tmp=*st.begin();
pos=mp[tmp];
int pos1=rfin(pos+1);
int pos2=lfin(pos-1);
//cout<<cnt<<endl;
//cout<<pos<<" "<<tmp<<endl;cout<<"pos1"<<pos1<<endl;cout<<"pos2"<<pos2<<endl;
cnt++;
lfather[pos]=lfin(pos-1);
rfather[pos]=rfin(pos+1);
st.erase(tmp);
ans[pos]=x%2;
int cnt1=0;
int cnt2=0;
while(cnt1<k&&pos1<=n)
{
cnt1++;
cnt++;
ans[pos1]=x%2;
st.erase(a[pos1]);//删除
rfather[pos1]=rfin(pos1+1);//并查集合并
lfather[pos1]=lfin(pos1-1);
pos1=rfin(pos);
}
while(cnt2<k&&pos2>=1)
{
cnt2++;
cnt++;
ans[pos2]=x%2;
st.erase(a[pos2]);
lfather[pos2]=lfin(pos2-1);
rfather[rfin(pos2)]=rfin(pos2+1);
pos2=lfin(pos);
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==0) printf("2");
else printf("%d",ans[i]);
}
printf("\n");
} 详细请见：https://blog.csdn.net/caowenbo2311694605/article/details/89358507
京公网安备 11010502036488号