题解 | #小欧安排座位#

解题思路

将小朋友们按照独特性进行分类。
独特性的全部挪一个位置。
不独特的坐回自己的位置。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> a,b;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	int n,i,x=-1,y=0;
	cin>>n>>s;
	for(i=1;i<=n;++i)
	{
		if(s[i-1]=='0')
			a.emplace_back(i);
		else
			b.emplace_back(i);
	}
	for(i=1;i<=n;++i)
	{
		if(s[i-1]=='0')
		{
			x=(x+1)%a.size();
			cout<<a[x]<<' ';
		}
		else
		{
			y=(y+1)%b.size();
			cout<<b[y]<<' ';
		}
	}
	return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),i,x=-1,y=0;
        String s=sc.next();
        ArrayList<Integer> a=new ArrayList<>();
        ArrayList<Integer> b=new ArrayList<>();
        for(i=1;i<=n;++i){
            if(s.charAt(i-1)=='0')
                a.add(i);
            else
                b.add(i);
        }
        for(i=1;i<=n;++i){
            if(s.charAt(i-1)=='0'){
                x=(x+1)%a.size();
                System.out.print(a.get(x)+" ");
            }else{
                y=(y+1)%b.size();
                System.out.print(b.get(y)+" ");
            }
        }
    }
}

n=int(input())
s=input()
x=-1
y=0
a,b=[],[]
for i in range(1,n+1):
    if(s[i-1]=='0'):
        a.append(i)
    else:
        b.append(i)
for i in range(1,n+1):
    if(s[i-1]=='0'):
        x=(x+1)%len(a)
        print(a[x],end=' ')
    else:
        y=(y+1)%len(b)
        print(b[y],end=' ')

算法及复杂度

算法：模拟。
时间复杂度： $\mathcal{O}(n)$ 。
空间复杂度： $\mathcal{O}(n)$ 。