解题思路

这道题有一个秘密武器：字符也能比大小！

在电脑里，每个字符都有自己的编号，这个编号叫 ASCII 码。大写字母、小写字母都有，而且：

• 大写字母 A~Z 的 ASCII 码是 65~90；
• 小写字母 a~z 的 ASCII 码是 97~122。

所以在 C++ 里，我们可以直接写 a[i] > a[maxp] 来比较两个字符，编译器会自动拿它们的 ASCII 码来比。字符大，就是 ASCII 码大。

步骤很简单：

1. 读入 n 个字母，同时用 maxp 记录"目前 ASCII 码最大的字母在第几个位置"。
2. 输出的时候，从第一个字母开始，如果到了 maxp 这个位置，就先输出一个 '0'（插个队），再输出这个最大字母。
3. 别忘了字符之间用空格分开。

打个比方：一排小朋友按字母大小排队，最大的那个字母"插队"前，老师先放了一个牌子"0"标记它，然后再按顺序报名字。

参考代码

// P4473 最大的字符：找出ASCII码最大的字母，在该字母前面插入字符'0'后输出所有字符
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    char a[1005];
    int maxp = 0;  // ASCII码最大字母的位置
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > a[maxp]) maxp = i;  // 字符可以直接比大小（按ASCII码）
    }
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';            // 除了第一个，前面加空格
        if (i == maxp) cout << '0' << ' ';  // 最大字母前面插入'0'
        cout << a[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

• 时间：读入一遍找最大字母是 O(n)，输出一遍是 O(n)，总时间 O(n)。
• 空间：用数组存了 n 个字母，是 O(n)。