杨校老师课堂之桶排序——桶计数

原创

杨校

发布于 2025-07-03 10:04:06

11800

代码可运行

文章被收录于专栏：C++信息学奥赛C++信息学奥赛

运行总次数：0

代码可运行

一、涉及知识点

(一) 基础语法与数据结构

数组的定义与初始化
- 静态数组声明：int a[15] = {0}; 定义了长度为 15 的数组（下标 0-14），初始值全为 0。
- 数组的作用：用数组下标映射 “数字本身”（如 a[3] 对应数字 3 的出现次数），实现 “值→下标” 的直接关联。
变量与输入输出
- 整型变量 t 用于临时存储输入的数字。
- 标准输入 cin >> t 和输出 cout 的基本用法，包括格式化输出（如 i << ":" << a[i]）。

(二) 循环结构的应用

for 循环的两种典型用法
- 计数循环（输入阶段）：for (int i = 1; i <= 50; i++) 控制读取 50 个输入，通过 a[t]++ 完成次数累加（每输入一个数字 t，对应位置的计数 + 1）。
- 遍历循环（输出阶段）：for (int i = 1; i <= 10; i++) 遍历 1-10 的数字，输出每个数字及其对应的出现次数（第一套代码）；或在遍历中查找最大值（第二套代码）。

(三) 核心算法思想

频率统计（计数思想）
- 核心逻辑：用数组作为 “计数器”，通过 a[t]++ 实现对每个数字出现次数的累加。
- 优势：时间复杂度为 O (n)（n 为输入数量），比用嵌套循环统计更高效。
最值查找（比较思想）
- 第二套代码专属：通过 max 记录当前最大次数，flag 记录对应数字，遍历过程中不断更新最值（if (a[i] > max)），最终找到出现次数最多的数字。

二、专项训练

1. 展品投票

参观完博物馆之后，同学们意犹未尽，纷纷讨论起自己看到的最棒的展品，老师看到同学们讨论如此热烈便提出一个问题，要求同学们给自己喜欢的展品进行投票。

现在老师挑选出10件展品，编号1~10，由50位同学进行投票，投票过程结束之后计算出每件展品的得票情况。

【输入格式】

输入一行，50个数字，表示50位同学的投票情况

【输出格式】

输出展品的编号以及这件展品的得票数。

【输入样例】

7 2 5 6 1 2 8 9 2 8 3 3 9 9 4 3 1 9 4 5 3 9 1 6 4 8 3 9 1 7 1 7 1 2 3 2 5 4 1 2 6 4 7 9 4 6 10 5 7 7

【输出样例】

1:7

2:6

3:6

4:6

5:4

6:4

7:6

8:3

9:7

10:1

#include <iostream>

using namespace std;

int a[15] = {0};  // 定义数组a，用于统计1-10每个数字出现的次数，初始化为0

int main() {
    int t;
    
    // 统计阶段：读取50个输入，统计每个数字出现的次数
    for (int i = 1; i <= 50; i++) {
        cin >> t;    
        a[t]++;  // 将数字t对应的计数加1（例如t=3时，a[3]的值+1）
    }
    
    // 输出阶段：遍历1-10，输出每个数字及其出现次数
    for (int i = 1; i <= 10; i++) {
        cout << i << ":" << a[i] << endl;  // 格式：数字:次数
    }
    
    return 0;
}

2. 展品投票（改进）

【题目描述】

现在老师挑选出10件展品，编号1~10，由50位同学进行投票，投票过程结束之后计算出得票最高的展品编号及票数。

【输入格式】

输入一行，50个数字，表示50位同学的投票情况

【输出格式】

输出得票最高展品的编号以及这件展品的得票数，如有得票数相同的情况，输出编号最小的。

【输入样例】

7 2 5 6 1 2 8 9 2 8 3 3 9 9 4 3 1 9 4 5 3 9 1 6 4 8 3 9 1 7 1 7 1 2 3 2 5 4 1 2 6 4 7 9 4 6 10 5 7 7

【输出样例】

1:7

#include <iostream>

using namespace std;
    
int a[15] = {0};  // 定义数组a，用于统计1-10每个数字出现的次数，初始全为0

int main() {
    int t;
    
    // 统计阶段：读取50个输入，统计每个数字出现的次数
    for (int i = 1; i <= 50; i++) {
        cin >> t;    
        a[t]++;  // 将数字t对应的计数加1（例如t=3时，a[3]的值+1）
    }
    
    // 查找最大值阶段：遍历数组a，找出出现次数最多的数字
    int max = 0;  // 记录最大次数
    int flag = 0; // 记录对应数字
    
    for (int i = 1; i <= 10; i++) {
        if (a[i] > max) {  // 如果当前数字i的次数大于已记录的最大值
            max = a[i];    // 更新最大值
            flag = i;      // 记录对应的数字
        }
    }
    
    // 输出结果：出现次数最多的数字及其次数
    cout << flag << ":" << max << endl;
    
    return 0;
}

3. 展品投票（进阶）

【题目描述】

老师带领n(1<=n<=10000)位同学去博物馆参观，参观完毕之后要挑选出最受欢迎的展品。已知参与投票的展品有m(1<=m<=200)件，请找出得票最多的展品，如果有多件展品得票数并列，则按照编号从小到大的顺序输出。

【输入格式】

输入共两行，第一行，两个数字n和m。第二行，n个数字，分别表示n位同学的投票情况。

【输出格式】

输出若干行，每行一个整数，表示得票最多的展品编号。

【输入样例】

10 4

3 2 3 1 2 1 3 4 2 4

【输出样例】

2

3

#include<iostream>  // 包含输入输出流头文件，用于输入输出操作
using namespace std;  // 使用标准命名空间，方便使用其中的函数和对象

int main(){  // 主函数，程序的入口
    int a[205] = {0};  // 定义一个大小为205的整型数组a，并初始化为0
    int n,m,x;  // 定义三个整型变量n、m、x，用于存储输入的数据
    cin>>n>>m;  // 从标准输入读取两个整数分别赋值给n和m

    for(int i = 1; i <= n; ++i) {  // 循环n次，从1到n
        cin>>x;  // 从标准输入读取一个整数赋值给x
        a[x]++;  // 将数组a中下标为x的元素值加1
    }

    int maxx = 0;  // 定义一个变量maxx，用于存储最大值，初始化为0

    for(int i = 1; i <= m; ++i) {  // 循环m次，从1到m
        if(a[i] > maxx) {  // 如果数组a中下标为i的元素值大于maxx
            maxx = a[i];  // 将maxx更新为该元素值
        }
    }

    for(int i = 1; i <= m; ++i) {  // 再次循环m次，从1到m
        if(a[i] == maxx) {  // 如果数组a中下标为i的元素值等于maxx
            cout<<i<<endl;  // 输出该下标i，并换行
        }
    }

    return 0;  // 主函数返回0，表示程序正常结束
}

签到问题（进阶）

【题目描述】

老师带领n(n<=1000)位同学去博物馆参观，这n位同学编号1~n。

通过签到确定已经有m(1<=m<=n)位同学到达，请输出未到达同学的编号。

【输入格式】

输入共两行，第一行，两个数字n和m。

第二行，m个数字，分别表示已经签到同学的编号

【输出格式】

输出一行，若干个整数，表示未签到同学的编号，按照从小到大的顺序输出。

【输入样例】

5 3

2 4 5

【输出样例】

1 3

#include<iostream>  // 包含输入输出流头文件，用于输入输出操作
using namespace std;  // 使用标准命名空间，方便使用其中的函数和对象

int main(){  // 主函数，程序的入口
    int a[1005] = {0};  // 定义一个大小为1005的整型数组a，并初始化为0
    int n,m,t;  // 定义三个整型变量n、m、t，用于存储输入的数据
    cin>>n>>m;  // 从标准输入读取两个整数分别赋值给n和m

    for(int i = 1; i <= m; ++i) {  // 循环m次，从1到m
        cin>>t;  // 从标准输入读取一个整数赋值给t
        ++a[t];  // 将数组a中下标为t的元素值加1
    }

    for(int i = 1; i <= n; ++i) {  // 循环n次，从1到n
        if(a[i] == 0) {  // 如果数组a中下标为i的元素值为0
            cout<<i<<" ";  // 输出该下标i，并输出一个空格
        }
    }

    return 0;  // 主函数返回0，表示程序正常结束
}

歌王争霸

题目描述

学校举办“我为学校歌唱”歌唱比赛，共有20名歌手进入了决赛。20名歌手逐个展示自己的才艺之后，由10位评委投票。为了方便，校艺术团为这20名歌手按照半决赛时的成绩高低从1~20进行编号，这样，评委只要用编号进行投票即可。最终得票最高者将会获得“校园歌王”荣誉称号，可以获得由校艺术团提供的大奖一份，并可以参与学校校歌MV的录制。现在，校艺术团的负责人找到你，邀请你写一个程序来帮助校艺术团统计出谁是歌王。

输入描述

输入10个编号，分别代表10位评委的选票。

输出描述

得票最高者的编号以及得票，中间用空格隔开。

样例

输入

2 15 9 17 3 16 13 16 7 11

输出

16 2

提示

注意：若出现票数相同情况，则谁的编号靠前谁赢得此次比赛。

#include<iostream>  // 包含输入输出流头文件，用于输入输出操作
using namespace std;  // 使用标准命名空间，方便使用其中的函数和对象
 int a[21] = {0}； // // 定义一个大小为21的整型数组a并初始化为0
int main(){  // 主函数，程序的入口
   int t;  //一个整型变量t
    for(int i = 1; i <= 10; ++i){  // 循环10次，从1到10
        cin>>t;  // 从标准输入读取一个整数赋值给t
        ++a[t];  // 将数组a中下标为t的元素值加1
    }

    int maxx = 0, flag;  // 定义一个变量maxx用于存储最大值并初始化为0，以及一个变量flag
    for(int i = 1; i <= 20; ++i){  // 循环20次，从1到20
        if(a[i] > maxx){  // 如果数组a中下标为i的元素值大于maxx
            maxx = a[i];  // 更新maxx为该元素值
            flag = 1;  // 将flag置为1，表示找到了更大的值
        }
    }

    cout<<flag<<" "<<maxx<<endl;  // 输出flag和maxx的值，并换行
    return 0;  // 主函数返回0，表示程序正常结束
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++14