小欧安排座位

[题目链接](https://www.nowcoder.com/practice/f90a4314d03f434f93f54b918304f97e)

思路

本题要求给 个小朋友安排座位（1 到 的排列），使得满足偏好的小朋友数量最多。偏好分两种：

  • 0：希望座位号等于自己的编号（不独特）
  • 1：希望座位号不等于自己的编号（独特）

贪心构造

核心观察：先让所有人坐在自己编号对应的座位上（即 ），这样所有 0 类小朋友都已满足。接下来只需处理 1 类小朋友。

关键问题：如何让所有 1 类小朋友的座位号都不等于自己的编号？

做法：收集所有 1 类小朋友的下标，对这些位置做一次循环右移（cyclic shift）：

$$

这样每个 1 类小朋友的座位号都变成了另一个 1 类小朋友的编号，必然不等于自己的编号。同时 0 类小朋友的座位不受影响。

特殊情况：如果 1 类小朋友只有 1 个，无法通过内部交换让其满足（和任何 0 类交换只会让一方满足、另一方不满足，总满足数不变）。此时最优解就是让所有人坐自己的位置，满足 个小朋友。

举例

以样例 n=5, s="00110" 为例：

步骤 座位安排 说明
初始 1 2 3 4 5 所有人坐自己的位置
收集 1 的位置 下标 2, 3 第 3、4 号小朋友想独特
循环右移 1 2 4 3 5 位置 2 和 3 互换座位号

所有 5 个小朋友的偏好都被满足。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    char s[200005];
    scanf("%s", s);

    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = i + 1;

    vector<int> ones;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') ones.push_back(i);
    }

    if (ones.size() >= 2) {
        int first_val = ans[ones[0]];
        for (int j = 0; j < (int)ones.size() - 1; j++) {
            ans[ones[j]] = ans[ones[j + 1]];
        }
        ans[ones.back()] = first_val;
    }

    for (int i = 0; i < n; i++) {
        printf("%d%c", ans[i], " \n"[i == n - 1]);
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = i + 1;

        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') ones.add(i);
        }

        if (ones.size() >= 2) {
            int firstVal = ans[ones.get(0)];
            for (int j = 0; j < ones.size() - 1; j++) {
                ans[ones.get(j)] = ans[ones.get(j + 1)];
            }
            ans[ones.get(ones.size() - 1)] = firstVal;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()

ans = list(range(1, n + 1))

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

if len(ones) >= 2:
    first_val = ans[ones[0]]
    for j in range(len(ones) - 1):
        ans[ones[j]] = ans[ones[j + 1]]
    ans[ones[-1]] = first_val

print(*ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const s = lines[1];

    const ans = Array.from({length: n}, (_, i) => i + 1);

    const ones = [];
    for (let i = 0; i < n; i++) {
        if (s[i] === '1') ones.push(i);
    }

    if (ones.length >= 2) {
        const firstVal = ans[ones[0]];
        for (let j = 0; j < ones.length - 1; j++) {
            ans[ones[j]] = ans[ones[j + 1]];
        }
        ans[ones[ones.length - 1]] = firstVal;
    }

    console.log(ans.join(' '));
});

复杂度分析

  • 时间复杂度：，遍历字符串一次，循环移位一次。
  • 空间复杂度：，存储答案数组和 1 类位置列表。