传送
题意:将n个人分成2个队,每次选取队伍中未被选取的最大值,然后顺便选取左边相邻的k个数(有多少拿多少) 问你最后队伍的分配情况。
#include<bits/stdc++.h>using namespace std;const int maxn=2e5+10;int a[maxn];struct node{int val;int id;}r[maxn];int per[maxn];int nxt[maxn];int cmp(node aa,node bb){return aa.val>bb.val;}int main(){memset(per,0,sizeof(per));memset(nxt,0,sizeof(nxt));map<int,int>mp;int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&r[i].val);r[i].id=i;nxt[i]=i+1;per[i]=i-1;}sort(r+1,r+1+n,cmp);int cnt=1;for(int i=1;i<=n;i++){if(mp[r[i].id]){continue;}int ll;mp[r[i].id]=cnt;ll=per[r[i].id];int kk=k;while(ll>0&&kk){if(!mp[ll]){mp[ll]=cnt;kk--;}ll=per[ll];}kk=k;int rr;rr=nxt[r[i].id];while(rr<=n&&kk){if(!mp[rr]){mp[rr]=cnt;kk--;}rr=nxt[rr];}per[rr]=ll;nxt[ll]=rr;if(cnt==1)cnt=2;elsecnt=1;}for(int i=1;i<=n;i++){printf("%d",mp[i]);}printf("\n");return 0;}