CF1154E. Two Teams(双向链表，模拟)

传送门：CF1154E. Two Teams

题意：给出n个人的能力值，且每个值互不相同，有两个序号为1和2的leader要挑人，每次的挑选都是先1后2，每次每个leader都会优先挑选能力值最大的人，以及这个人左右两侧各k个人（若不到k个则全部取完）直到所有人都被挑选完毕。输出每个选手会被分配到的leader序号。

解析：这个问题可以转化为一个序列每次取走最大的一个数以及这个数两侧k个数，直到序列长度为0，因此可以看作一个链表的模拟过程，每次取走一段后将这一段的前一个结点的尾指针指向这一段的后一个结点，以及将这一段的后一个结点的头指针指向这一段的前一个结点，这个过程可以用数组来模拟，定义l[i],r[i]数组分别表示当前下标为i的结点指向的后一位与前一位的结点的下标，是一道双向链表模拟的简单题。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<queue>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 2e5+5;
int l[maxn];
int r[maxn];
int a[maxn];
int vis[maxn];
int ans[maxn];
priority_queue<pair<int, int> > q;

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < n; i++) l[i] = i + 1, r[i] = i - 1;
	for (int i = 0; i < n; i++) q.push(make_pair(a[i], i));
	int now = 1;
	while (!q.empty()) {
		if (vis[q.top().second]) {
			q.pop();
			continue;
		}
		int y = q.top().second;
		q.pop();
		vis[y] = 1;
		ans[y] = now;
		int cnt = 0;
		int xx = -1, yy = n;
		for (int i = l[y]; i < n && cnt < k; i = l[i]) {
			cnt++;
			vis[i] = 1;
			ans[i] = now;
			if (cnt == k) yy = l[i];
		}
		cnt = 0;
		for (int i = r[y]; i >= 0 && cnt < k; i = r[i]) {
			cnt++;
			vis[i] = 1;
			ans[i] = now;
			if (cnt == k) xx = r[i];
		}
		if (xx != -1) l[xx] = yy;
		if (yy != n) r[yy] = xx;
		now = now % 2 + 1;
	}
	for (int i = 0; i < n; i++) printf("%d", ans[i]);
	return 0;
}