首页 > 试题广场 >

小欧安排座位

[编程题]小欧安排座位

热度指数：1147 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小欧现在有 $n$ 个小朋友，同时有 $n$ 个座位。小欧现在要给他们安排座位， $n$ 个小朋友中有一些希望自己是独特的，另一些小朋友则希望自己是不独特的。
当一个小朋友是独特的当且仅当小朋友自身的编号与座位的编号不相等，否则这个小朋友就是不独特的。

现在给你 $n$ 个小朋友的需求，你需要给他们安排座位，满足尽可能多的小朋友的需求。

输入描述:

第一行一个整数表示小朋友的数量。
第二行输入一个长度为只包含 0 和 1 的字符串，第位若为 1 代表第个小朋友希望自己是独特的，否则他希望自己是不独特的。

输出描述:

个用空格隔开的整数，第个表示第个小朋友的位置。若有多种安排方案，输出任意一个即可。

示例1

输入

5
00110

输出

1 2 4 3 5

说明

这样安排满足了所有小朋友的需求

示例2

输入

2
01

输出

1 2

说明

只能满足 1 个小朋友的需求

算法知识视频讲解

C++

我也想AC

```

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int a[N];

bool st[N];

int b[N];

signed main()

{

int n;

cin >> n;

string s;

cin >> s;

int k = s.size();

s = " " + s;

int m = 0;

for(int i = 1; i <= k;i++) if(s[i] == '1') st[i] = 1,b[++m] = i;

sort(b + 1,b + n + 1);

reverse(b + 1, b + n + 1);

int kk = 0;

if(m%2 == 0)

{

for(int i = 1; i <= n;i++)

{

if(st[i] == 0) a[i] = i;

else a[i] = b[++kk];

}

else

{

int k = m/2 + 1;

int ll = 0;

int kk = 0;

for(int i = 1; i <= n; i++)

{

if(st[i] == 0) a[i] = i;

else

{

if(ll == 0)

{

ll = 1;

a[i] = b[k];

b[k] = 0;

sort(b + 1,b + n + 1);

reverse(b + 1,b + n + 1);

}

else

{

a[i] = b[++kk];

}

for(int i = 1; i <= n; i++) cout << a[i] << " ";

}

```

发表于 2024-11-20 21:30:12 回复(0)

牛客45984699号

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int a;
    cin >> a;
    string vt;
    map<int, int> mp;
    cin >> vt;
    int j=0,n = 0;
    for (char k : vt) {
        if (k == '1') {
            mp[n] = j+1;
            n++;
       }
        j++;
    }
     n = 1;
    j = 0;
    for (char k : vt) {
        if (k == '0') {
            cout << j+1<<" ";
        }
        else {
            if (n >= mp.size()) {
                n = 0;
            }
            cout << mp[n]<<" ";
            n++;
        }

        j++;
    }

}
// 64 位输出请用 printf("%lld")

发表于 2025-02-10 20:12:05 回复(0)

立羽昕玥

解释参考答案里的：
x=(x+1)%len(a)

是一种取模运算，确保索引在列表 a 的范围内循环。例如，如果 a = [1, 2, 3]，x 的值会依次为 0, 1, 2, 0, 1, 2, ...

发表于 2024-11-27 15:17:18 回复(0)

k3ats

n = int(input())

s = input()

ans = [i + 1 for i in range(n)]

# 找到需要独特的朋友位置

unique_indices = [i for i in range(n) if s[i] == '1']

# 如果有独特需求的朋友，进行位置交换

if unique_indices:

# 进行位置轮换，使每个有独特需求的朋友不在原位置

last_value = ans[unique_indices[-1]]

for i in range(len(unique_indices) - 1, 0, -1):

ans[unique_indices[i]] = ans[unique_indices[i - 1]]

ans[unique_indices[0]] = last_value

print(*ans)

发表于 2024-11-21 14:37:24 回复(0)

月薪三千啊

n = int(input())

s = input()

ans = [i + 1 for i in range(n)]

st = []
for i in range(n):
    if s[i] == "1":
        st.append([i + 1, i])

tmp = st[0][0]
for i in range(len(st) - 1):
    st[i][0] = st[i + 1][0]

st[-1][0] = tmp

# print(st)
for x, y in st:
    ans[y] = x

print(*ans)

发表于 2024-11-20 14:15:14 回复(0)