蓝桥杯 C++ 算法入门：洛谷 P1598《垂直柱状图》——计数数组与模拟

一、题目来源

• 题目名称： P1598 [USACO03FEB] 垂直柱状图（Vertical Histogram）
• 题目链接： https://www.luogu.com.cn/problem/P1598
• 知识点： 字符串、数组统计、循环、模拟、格式化输出
• 难度定位： 基础算法入门
• 练习目标： 掌握字符出现次数统计，并学会用嵌套循环输出垂直直方图。

说明：这是一道经典算法练习题，并非蓝桥杯官方真题。通过这道题，可以训练蓝桥杯 C++ B 组需要的基础编程能力。

二、题目描述

输入四行文本，统计其中每个大写英文字母 A 到 Z 出现的次数，并将统计结果绘制成垂直直方图。

每个字母对应一列，字母出现一次，就在对应列中增加一个星号 *。

输出要求：

1. 直方图从最高的一层开始输出。
2. 每个字母对应的星号数量等于它的出现次数。
3. 星号不足的位置使用空格占位。
4. 最后一行按照字母顺序输出 A B C ... Z。
5. 每行末尾不能有多余空格，也不能输出额外的空行。

核心问题：如何先统计字母出现次数，再把统计结果转换成竖直方向的星号图形？

三、解题思路

整个程序可以分为四个步骤。

1. 使用数组统计字母次数

由于英文字母一共只有 26 个，可以定义一个长度为 26 的整数数组：

int cnt[26] = {0};

其中：

• cnt[0] 表示字母 A 的出现次数。
• cnt[1] 表示字母 B 的出现次数。
• cnt[2] 表示字母 C 的出现次数。
• ……
• cnt[25] 表示字母 Z 的出现次数。

利用字符编码，可以通过下面的表达式将字母转换为数组下标：

cnt[ch - 'A']++;

例如：

'A' - 'A'  // 结果为 0
'B' - 'A'  // 结果为 1
'C' - 'A'  // 结果为 2

当遇到字母 C 时，cnt[ch - 'A']++ 实际上就是 cnt[2]++，表示 C 的出现次数加一。

由于输入是四行文本，因此需要循环读取四行，再遍历每一行中的字符。

for (int i = 0; i < 4; i++) {
    getline(cin, s);

    for (char ch : s) {
        if (ch >= 'A' && ch <= 'Z') {
            cnt[ch - 'A']++;
        }
    }
}

这里使用 getline() 读取整行，能够保留空格等字符。通过判断字符是否处于 'A' 到 'Z' 之间，可以避免将其他字符错误地作为数组下标。

2. 找到直方图的最大高度

直方图的总高度由出现次数最多的字母决定。

例如：

字母	出现次数
A	4
B	1
C	2

A 出现了 4 次，因此直方图需要输出 4 层星号。

代码如下：

int maxn = 0;

for (int i = 0; i < 26; i++) {
    if (cnt[i] > maxn) {
        maxn = cnt[i];
    }
}

也可以使用 max() 更新最大值：

maxn = max(maxn, cnt[i]);

3. 使用嵌套循环输出直方图

这是整道题最重要的部分。

外层循环控制高度，从最大值逐渐减小到 1：

for (int h = maxn; h >= 1; h--)

内层循环依次检查每个字母：

if (cnt[j] >= h) {
    cout << '*';
} else {
    cout << ' ';
}

判断规则是：

• 如果某个字母的出现次数大于等于当前高度，就输出 *。
• 否则输出空格。

为什么要使用 cnt[j] >= h？

假设 A 出现 4 次，那么它应该在第 4、3、2、1 层都有星号。

当 h = 4 时，cnt[A] >= 4 成立。

当 h = 3 时，cnt[A] >= 3 仍然成立。

一直到 h = 1，A 都应该输出星号。

注意：每两列之间需要一个空格，但是每行末尾不能出现多余空格。 因此，输出每个字母对应的列之前，应先确定当前行最后一个有星号的位置。

4. 输出最后一行的字母

完成所有星号输出后，再输出字母 A 到 Z：

for (int i = 0; i < 26; i++) {
    if (i > 0) {
        cout << ' ';
    }

    cout << char('A' + i);
}
cout << '\n';

这里使用 char('A' + i) 将数组下标转换成对应字母。

通过判断 i > 0，保证只有从第二个字母开始才输出分隔空格，从而避免最后一个字母 Z 后面出现多余空格。

四、完整 C++ 代码

下面是可以提交到洛谷的完整参考代码，使用 C++17 编译标准。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int cnt[26] = {0};
    string s;

    // 第一步：读取四行文本，统计字母次数
    for (int i = 0; i < 4; i++) {
        getline(cin, s);

        for (char ch : s) {
            if (ch >= 'A' && ch <= 'Z') {
                cnt[ch - 'A']++;
            }
        }
    }

    // 第二步：寻找直方图最大高度
    int maxn = 0;

    for (int i = 0; i < 26; i++) {
        if (cnt[i] > maxn) {
            maxn = cnt[i];
        }
    }

    // 第三步：从最高层向下输出星号
    for (int h = maxn; h >= 1; h--) {
        // 找到当前行最后一个需要输出星号的位置
        int last = 25;

        while (last >= 0 && cnt[last] < h) {
            last--;
        }

        // 输出当前行，避免行尾多余空格
        for (int j = 0; j <= last; j++) {
            if (j > 0) {
                cout << ' ';
            }

            if (cnt[j] >= h) {
                cout << '*';
            } else {
                cout << ' ';
            }
        }

        cout << '\n';
    }

    // 第四步：输出 A 到 Z
    for (int i = 0; i < 26; i++) {
        if (i > 0) {
            cout << ' ';
        }

        cout << char('A' + i);
    }

    cout << '\n';

    return 0;
}

五、样例演示

下面是一个用于理解算法的自定义样例，并非洛谷官方样例。

输入

ABC
A
AC
A

统计结果

字母	出现次数
A	4
B	1
C	2

其他字母的出现次数均为 0。

输出

*
*
*   *
* * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

输出过程分析

当 h = 4 时，只有 A 出现了 4 次，因此输出：

*

当 h = 3 时，仍然只有 A 满足条件：

*

当 h = 2 时，A 和 C 满足条件，B 不满足条件：

*   *

当 h = 1 时，A、B、C 都满足条件：

* * *

最后输出字母表：

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

六、HTML 动画演示

为了更直观地理解直方图的生成过程，可以使用下面的 HTML 页面。

动画使用 A、B、C 三个字母作为演示数据，分别出现 4 次、1 次、2 次。页面会逐行显示星号，模拟程序从最高层向下输出的过程，并提供重新播放按钮。

使用方法：

1. 复制下面全部 HTML 代码。
2. 保存为 histogram-animation.html。
3. 使用浏览器打开文件，即可观看动画。
4. 修改 counts 数组中的数值，可以观察不同统计结果对应的直方图。

<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>垂直柱状图动画演示</title>

    <style>
        body {
            font-family: Arial, sans-serif;
            max-width: 680px;
            margin: 40px auto;
            padding: 20px;
            background: #f5f7fb;
            color: #243047;
        }

        .card {
            background: white;
            padding: 24px;
            border-radius: 14px;
            box-shadow: 0 4px 18px rgba(0, 0, 0, 0.08);
        }

        h1 {
            font-size: 24px;
        }

        .description {
            color: #667085;
            line-height: 1.8;
        }

        #histogram {
            min-height: 150px;
            padding: 16px;
            background: #101828;
            color: #6ee7b7;
            border-radius: 8px;
            font-family: Consolas, monospace;
            font-size: 20px;
            line-height: 1.7;
            white-space: pre;
            overflow-x: auto;
        }

        .line {
            animation: appear 0.4s ease-out both;
        }

        @keyframes appear {
            from {
                opacity: 0;
                transform: translateY(8px);
            }
            to {
                opacity: 1;
                transform: translateY(0);
            }
        }

        button {
            margin-top: 18px;
            padding: 10px 18px;
            border: none;
            border-radius: 8px;
            background: #2563eb;
            color: white;
            cursor: pointer;
            font-size: 15px;
        }

        button:hover {
            background: #1d4ed8;
        }

        .note {
            margin-top: 16px;
            font-size: 13px;
            color: #667085;
        }
    </style>
</head>

<body>
    <div class="card">
        <h1>垂直柱状图动画演示</h1>

        <p class="description">
            演示数据：A 出现 4 次，B 出现 1 次，C 出现 2 次。
            程序从最高层开始，逐层输出星号。
        </p>

        <div id="histogram" aria-live="polite"></div>

        <button id="replay">重新播放动画</button>

        <p class="note">
            观察每一层：当字母的出现次数大于等于当前高度时，
            对应位置输出星号，否则输出空格。
        </p>
    </div>

    <script>
        // 每个数字表示对应字母出现的次数
        const letters = ["A", "B", "C"];
        const counts = [4, 1, 2];

        const histogram = document.getElementById("histogram");
        let timers = [];

        // 根据统计结果生成直方图的每一行
        function buildLines() {
            const maxCount = Math.max(...counts);
            const lines = [];

            for (let h = maxCount; h >= 1; h--) {
                // 找到当前行最后一个有星号的位置
                let last = counts.length - 1;

                while (last >= 0 && counts[last] < h) {
                    last--;
                }

                let line = "";

                for (let j = 0; j <= last; j++) {
                    if (j > 0) {
                        line += " ";
                    }

                    if (counts[j] >= h) {
                        line += "*";
                    } else {
                        line += " ";
                    }
                }

                lines.push(line);
            }

            // 最后一行输出字母标签
            lines.push(letters.join(" "));

            return lines;
        }

        // 逐行播放
        function playAnimation() {
            timers.forEach(timer => clearTimeout(timer));
            timers = [];

            histogram.innerHTML = "";

            const lines = buildLines();

            lines.forEach((line, index) => {
                const timer = setTimeout(() => {
                    const row = document.createElement("div");
                    row.className = "line";
                    row.textContent = line;

                    histogram.appendChild(row);
                }, index * 550);

                timers.push(timer);
            });
        }

        document.getElementById("replay")
            .addEventListener("click", playAnimation);

        // 页面加载后自动播放
        playAnimation();
    </script>
</body>
</html>

注意：CSDN 正文通常会将代码块中的 HTML 和 JavaScript 作为文本展示，不一定允许直接运行。将代码保存为独立 HTML 文件，就可以在浏览器中查看动画。

七、常见错误总结

1. 忘记使用 getline()

cin >> s;

cin >> s 通常只读取空白字符之前的内容。如果需要读取整行文本，应使用：

getline(cin, s);

2. 数组下标计算错误

错误写法：

cnt[ch]++;

如果直接将字符作为下标，会访问 ASCII 编码对应的位置，而不是 0 到 25 之间的字母位置。

正确写法：

cnt[ch - 'A']++;

3. 直方图从下往上输出

题目要求从最高层向下输出，因此高度应该逐渐减小：

for (int h = maxn; h >= 1; h--)

4. 判断条件写错

正确判断是：

if (cnt[j] >= h)

因为出现次数为 4 的字母，不仅要在第 4 层输出星号，还要在第 3、2、1 层输出星号。

如果错误地写成 cnt[j] == h，每个字母只会输出一颗星，无法形成柱状图。

5. 忽略行尾空格

输出格式也是本题的重要考点。

如果每一列后面都直接输出空格，最后一列之后可能留下多余空格。可以通过确定当前行最后一个有星号的位置，避免输出多余的尾随空格。

八、时间复杂度与空间复杂度

设四行文本的字符总数为 N，出现次数最多的字母出现了 H 次。

• 统计阶段： 遍历所有输入字符，时间复杂度为 O(N)。
• 寻找最大值： 遍历 26 个数组元素，时间复杂度为 O(26)。
• 绘制直方图： 每层最多检查 26 个字母，时间复杂度为 O(26H)。

因此，总时间复杂度可以写为：

O(N + 26H)

由于英文字母数量固定为 26，空间复杂度为 O(1)（不计输入字符串本身的存储空间）。

九、这道题能学到什么？

通过这道题，我总结出四个重要知识点：

1. 计数数组： 使用数组下标记录不同字符出现的次数。
2. 字符与整数转换： 理解 ch - 'A' 和 char('A' + i) 的含义。
3. 嵌套循环： 外层控制高度，内层遍历每个字母。
4. 输出格式控制： 注意空格、换行和行尾多余字符。

这道题虽然没有复杂的算法，但能很好地训练字符串处理、数组统计、循环控制和模拟输出能力。

对于正在准备蓝桥杯 C++ B 组的同学，建议先独立完成计数部分，再自己编写最大值查找和星号输出循环，不要一开始就直接复制完整代码。

十、下一步练习

完成这道题后，可以继续练习：

• 字母出现次数统计；
• 数字频率统计；
• 数组最大值与最小值；
• 字符串模拟；
• 嵌套循环打印图形；
• 蓝桥杯历年基础模拟题。

最后总结： 本题的核心不是统计字母本身，而是将统计结果转换成图形。掌握计数数组、最大值查找和分层输出之后，就可以将相同思路应用到许多基础模拟题中。

题目地址：https://www.luogu.com.cn/problem/P1598

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/aqiu111111/article/details/169368623