题目详解

问题描述

给定一个由小写字母 'z', 'e', 'r', 'o', 'n' 组成的字符串，长度 $n$（$1 \le n \le 10^5$）。保证可以重新排列这些字母，使得它们形成若干个单词，每个单词要么是 "zero"（对应数字 $0$），要么是 "one"（对应数字 $1$）。要求通过重新排列，得到一个最大的二进制数（用空格分隔每个二进制位，允许前导零），并输出这个二进制数。

问题分析

我们需要从打乱的字母中恢复出原始的数字序列。由于只有两种单词：

• "zero" 包含字母 z, e, r, o
• "one" 包含字母 o, n, e

注意字母 'z' 仅出现在 "zero" 中，字母 'n' 仅出现在 "one" 中。因此：

• 统计字符串中 'z' 的个数，就是数字 $0$ 的个数，记作 $cnt_0$。
• 统计字符串中 'n' 的个数，就是数字 $1$ 的个数，记作 $cnt_1$。

为了得到最大的二进制数，我们应该把所有 $1$ 放在前面，所有 $0$ 放在后面。因为二进制数比较时，高位（左边的位）权重更大，所以将 $1$ 尽可能前置可以得到最大值。例如，二进制数 "110" 大于 "101" 和 "011"。

解法步骤

1. 读入整数 $n$ 和字符串 $s$。
2. 遍历字符串 $s$，统计字符 'n' 的出现次数 $cnt_1$，统计字符 'z' 的出现次数 $cnt_0$。
3. 输出 $cnt_1$ 个 "1 "，然后输出 $cnt_0$ 个 "0 "。

正确性证明

• 唯一性：由于 'z' 只属于 "zero"，每个 "zero" 贡献一个 'z'，所以 'z' 的个数就是 "zero" 的个数，即数字 $0$ 的个数。同理，'n' 只属于 "one"，所以 'n' 的个数就是数字 $1$ 的个数。因此字母统计直接决定了数字的个数。
• 最大化：在二进制表示中，高位决定大小。为了使数值最大，应将所有 $1$ 放在高位（左边），所有 $0$ 放在低位（右边）。因此先输出 $cnt_1$ 个 1，再输出 $cnt_0$ 个 0 即可得到最大数。

时间复杂度

统计字母只需一次遍历，时间复杂度 $O(n)$，空间复杂度 $O(1)$。满足 $n \le 10^5$ 的限制。

示例验证

示例1
输入：

4
ezor

统计：'n' 出现 $0$ 次，'z' 出现 $1$ 次。输出 "0 "，正确。

示例2
输入：

10
nznooeeoer

统计：'n' 出现 $2$ 次，'z' 出现 $1$ 次。输出 "1 1 0 "，正确。

代码实现（标程）

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    int cnt1 = count(s.begin(), s.end(), 'n');
    int cnt0 = count(s.begin(), s.end(), 'z');
    for (int i = 0; i < cnt1; ++i) cout << "1 ";
    for (int i = 0; i < cnt0; ++i) cout << "0 ";
    return 0;
}

总结

本题的关键在于观察到字母 'z' 和 'n' 分别唯一地对应数字 $0$ 和 $1$，从而将问题简化为计数和按顺序输出。贪心地让 $1$ 在高位即可得到最大二进制数。