首页 > 试题广场 >

小欧安排座位

[编程题]小欧安排座位
  • 热度指数：207 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小欧现在有n个小朋友，同时有n个座位。小欧现在要给他们安排座位，n个小朋友中有一些希望自己是独特的，另一些小朋友则希望自己是不独特的。
当一个小朋友是独特的当且仅当小朋友自身的编号与座位的编号不相等，否则这个小朋友就是不独特的。

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

输入描述:
第一行一个整数n(1 \leq n \leq 10^5)表示小朋友的数量。
第二行输入一个长度为n只包含 0 和 1 的字符串，第i位若为 1 代表第i个小朋友希望自己是独特的，否则他希望自己是不独特的。


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

输入

5
00110

输出

1 2 4 3 5

说明

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

输入

2
01

输出

1 2

说明

只能满足 1 个小朋友的需求
算法知识视频讲解
添加回答
C++
我不想AC头像 我不想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)
k3ats头像 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)

发表于 今天 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)
提交观点

问题信息

难度：
3条回答 16浏览

热门推荐

相关试题

小欧安排座位

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号