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 DEBUGfreopen("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 DEBUGprintf("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 DEBUGfreopen("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];elsebreak;}for(int j=1;j<=k;j++){if(r!=0&&!ans[r])ans[r]=pos,r=nxt[r];elsebreak;}//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 DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Two Teams的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。