蓝桥杯 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 的整数数组：

intcnt[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(inti=0;i<4;i++){getline(cin,s);for(charch:s){if(ch>='A'&&ch<='Z'){cnt[ch-'A']++;}}}

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

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

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

例如：

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

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

代码如下：

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

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

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

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

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

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

for(inth=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(inti=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>usingnamespacestd;intmain(){intcnt[26]={0};string s;// 第一步：读取四行文本，统计字母次数for(inti=0;i<4;i++){getline(cin,s);for(charch:s){if(ch>='A'&&ch<='Z'){cnt[ch-'A']++;}}}// 第二步：寻找直方图最大高度intmaxn=0;for(inti=0;i<26;i++){if(cnt[i]>maxn){maxn=cnt[i];}}// 第三步：从最高层向下输出星号for(inth=maxn;h>=1;h--){// 找到当前行最后一个需要输出星号的位置intlast=25;while(last>=0&&cnt[last]<h){last--;}// 输出当前行，避免行尾多余空格for(intj=0;j<=last;j++){if(j>0){cout<<' ';}if(cnt[j]>=h){cout<<'*';}else{cout<<' ';}}cout<<'\n';}// 第四步：输出 A 到 Zfor(inti=0;i<26;i++){if(i>0){cout<<' ';}cout<<char('A'+i);}cout<<'\n';return0;}

五、样例演示

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

输入

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数组中的数值，可以观察不同统计结果对应的直方图。

<!DOCTYPEhtml><htmllang="zh-CN"><head><metacharset="UTF-8"><metaname="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 18pxrgba(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;}@keyframesappear{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><divclass="card"><h1>垂直柱状图动画演示</h1><pclass="description">演示数据：A 出现 4 次，B 出现 1 次，C 出现 2 次。 程序从最高层开始，逐层输出星号。</p><divid="histogram"aria-live="polite"></div><buttonid="replay">重新播放动画</button><pclass="note">观察每一层：当字母的出现次数大于等于当前高度时， 对应位置输出星号，否则输出空格。</p></div><script>// 每个数字表示对应字母出现的次数constletters=["A","B","C"];constcounts=[4,1,2];consthistogram=document.getElementById("histogram");lettimers=[];// 根据统计结果生成直方图的每一行functionbuildLines(){constmaxCount=Math.max(...counts);constlines=[];for(leth=maxCount;h>=1;h--){// 找到当前行最后一个有星号的位置letlast=counts.length-1;while(last>=0&&counts[last]<h){last--;}letline="";for(letj=0;j<=last;j++){if(j>0){line+=" ";}if(counts[j]>=h){line+="*";}else{line+=" ";}}lines.push(line);}// 最后一行输出字母标签lines.push(letters.join(" "));returnlines;}// 逐行播放functionplayAnimation(){timers.forEach(timer=>clearTimeout(timer));timers=[];histogram.innerHTML="";constlines=buildLines();lines.forEach((line,index)=>{consttimer=setTimeout(()=>{constrow=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(inth=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