【Codeforces 578E】Walking! | Mrsrz's blog

贪心。

题目大意：

给定一个 $01$ 序列 $a$，要求找到一个排列 $p$ 使得 $\forall i\in[1,n-1]$，满足 $a_{p_i}\neq a_{p_{i+1}}$。

要求 $p_i>p_{i+1}$ 的 $i$ 的个数尽可能少。

输出最少个数，并给出构造方案。

题解：

贪心。

每次找到一个能够匹配的进行匹配，找不到就自己新开一个。

最后将若干段进行合并，分类讨论即可。

这里匹配的时候要注意，对于一个位置，要找到之前的最靠前的匹配，这样才能保证能够正确匹配。否则类似 LRRL 的就会导致最后无法合并。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
#include<set>
#include<vector>
#include<deque>
#include<cstring>
using namespace std;
const int N=2e5+5;
set<int>st[2];
int n,cnt;
char s[N];
vector<int>res[N],id[4];
deque<int>L,R;
inline void out(vector<int>&v){for(int i:v)printf("%d ",i);}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i)
    if(s[i]=='L'){
        if(R.empty()){
            res[++cnt].push_back(i);
            L.push_back(cnt);
        }else{
            int x=R.front();
            res[x].push_back(i);
            L.push_back(x);
            R.pop_front();
        }
    }else{
        if(L.empty()){
            res[++cnt].push_back(i);
            R.push_back(cnt);
        }else{
            int x=L.front();
            res[x].push_back(i);
            R.push_back(x);
            L.pop_front();
        }
    }
    printf("%d\n",cnt-1);
    for(int i=1;i<=cnt;++i){
        const int zt=(s[res[i].front()]=='R')<<1|(s[res[i].back()]=='R');
        id[zt].push_back(i);
    }
    if(id[3].size()>id[0].size()){
        for(int i:id[2])out(res[i]);
        while(id[3].size()&&id[0].size()){
            int x=id[3].back();id[3].pop_back();
            out(res[x]);
            x=id[0].back();id[0].pop_back();
            out(res[x]);
        }
        while(id[3].size()){
            int x=id[3].back();id[3].pop_back();
            out(res[x]);
        }
        for(int i:id[1])out(res[i]);
    }else
    if(id[3].size()<id[0].size()){
        for(int i:id[1])out(res[i]);
        while(id[3].size()&&id[0].size()){
            int x=id[0].back();id[0].pop_back();
            out(res[x]);
            x=id[3].back();id[3].pop_back();
            out(res[x]);
        }
        while(id[0].size()){
            int x=id[0].back();id[0].pop_back();
            out(res[x]);
        }
        for(int i:id[2])out(res[i]);
    }else{
        for(int i:id[2])out(res[i]);
        while(id[3].size()>1&&id[0].size()>1){
            int x=id[3].back();id[3].pop_back();
            out(res[x]);
            x=id[0].back();id[0].pop_back();
            out(res[x]);
        }
        while(id[3].size()){
            int x=id[3].back();id[3].pop_back();
            out(res[x]);
        }
        for(int i:id[1])out(res[i]);
        while(id[0].size()){
            int x=id[0].back();id[0].pop_back();
            out(res[x]);
        }
    }
    return 0;
}