题解 CF1154E Two Teams

· · 题解

还没看到用 set 加双向链表做的。

思路

有以下要做到的点：

  1. 查询最大值。
  2. 删除已经被选择的人。
  3. 向左和右分别找 k 个人。

用 set 维护 1,2，用双向链表维护 3。
注意：删除一个人，需要在 set 和链表中同时删除。

由于每个数只会分别在 set 和链表中删除一次，所以时间复杂度为 O(n\log n)。

其他按要求模拟即可。

代码和提交记录

#include<bits/stdc++.h>
using namespace std;
int n,k,n1;
int ans[200003];
int p[200003];
struct node{
    int x,nxt,lst;
}l[200003];
int now=1;
set<int>s;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;   n1=n;
    for(int i=1;i<=n;i++){
        cin>>l[i].x;
        l[i].nxt=i+1;  l[i].lst=i-1;
        p[l[i].x]=i;//记录数字在哪个位置，方便查询。
        s.insert(l[i].x);
    }
    while(n1){//n1记录还剩多少人
        int x=*(--s.end());
        ans[p[x]]=now;
        for(int i=l[p[x]].nxt,j=1;i<=n&&j<=k;j++,i=l[i].nxt){//向右遍历
            n1--;
            ans[i]=now;
            s.erase(l[i].x);//这三行为删除
            l[l[i].nxt].lst=l[i].lst;
            l[l[i].lst].nxt=l[i].nxt;
        }
        for(int i=l[p[x]].lst,j=1;i>0&&j<=k;j++,i=l[i].lst){//向左遍历
            n1--;
            ans[i]=now;
            s.erase(l[i].x);
            l[l[i].nxt].lst=l[i].lst;
            l[l[i].lst].nxt=l[i].nxt;
        }
        n1--;
        s.erase(x);
        l[l[p[x]].nxt].lst=l[p[x]].lst;
        l[l[p[x]].lst].nxt=l[p[x]].nxt;
        now=now%2+1;
    }
    for(int i=1;i<=n;i++)cout<<ans[i];
    return 0;
}