练74.1  垂直直方图

解题思路

统计四行A～Z频次，从最大频次H向下绘制各层：频次≥层号输出星，否则空格。字母列间一空格，每行去掉末尾空格，最后字母表。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

忽略空白数字标点；不能输出顶部空行。

复杂度

输入S字符，时间O(S+26H)，空间O(S)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cnt[26] = {};
    string s;
    for (int i = 0; i < 4; i++) {
        getline(cin, s);
        for (char c : s)
            if (c >= 'A' && c <= 'Z')
                cnt[c - 'A']++;
    }
    int H = *max_element(cnt, cnt + 26);
    for (int h = H; h >= 1; h--) {
        string r;
        for (int i = 0; i < 26; i++) {
            if (i)
                r += ' ';
            r += cnt[i] >= h ? '*' : ' ';
        }
        while (!r.empty() && r.back() == ' ')
            r.pop_back();
        cout << r << "\n";
    }
    for (int i = 0; i < 26; i++) {
        if (i)
            cout << " ";
        cout << char('A' + i);
    }
    cout << "\n";
    return 0;
}