当前位置: 首页 > article >正文

PTA7-13 统计工龄

题目描述

给定公司 n 名员工的工龄,要求按工龄增序输出每个工龄段有多少员工。

输入格式:

输入首先给出正整数 n(≤105),即员工总人数;随后给出 n 个整数,即每个员工的工龄,范围在 [0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的员工个数,格式为:“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

题目分析 

首先,题目输入的是n个员工的工龄,每个工龄范围在0到50之间。输出需要按工龄递增的顺序,每个工龄的人数,如果人数为0就不输出。比如样例中的输入8个员工,工龄有10、2、0、5、7、2、5、2,输出的时候0出现1次,2出现3次,依此类推。

那怎么处理这个问题呢?首先,我想到的是,因为工龄的范围很小,只有0到50,所以可能不需要用普通的排序算法来处理。因为当数据范围有限的时候,计数排序(Counting Sort)可能是更高效的选择,尤其是当n很大的时候,比如题目中的n可以达到1e5,这时候计数排序的时间复杂度是O(n + k),其中k是工龄的范围,这里是51,所以总的时间复杂度是线性的,非常高效。

那具体来说,步骤应该是这样的:

1. 创建一个大小为51的数组count,用来统计每个工龄出现的次数。因为工龄的范围是0到50,所以数组下标0到50对应各个工龄,初始值都是0。

2. 遍历输入的工龄,对于每个工龄,对应的count数组的位置加1。

3. 遍历count数组,从0到50的顺序,如果某个位置的计数值大于0,就输出“工龄:人数”。

这样的话,整个过程的时间复杂度是O(n + 51),也就是O(n),对于n到1e5来说,完全没问题。而且空间上只需要一个固定大小的数组,所以空间复杂度也是O(1)的。

那这样的话,就不需要使用排序算法了,比如像上一题那样用标准库的sort函数。因为这里工龄的范围很小,用计数排序更高效。

那接下来需要考虑输入输出的问题。因为n可能很大,所以输入输出要尽量高效。C++中的cin和cout默认情况下可能比较慢,所以需要做一些优化。比如,可以关闭同步,使用更快的输入输出方式。比如用:

ios::sync_with_stdio(false);

cin.tie(nullptr);

这样可以加速输入输出。另外,在读取n个整数的时候,应该用循环逐个读入,然后统计到count数组中。

比如,输入样例中的情况,当输入8个数时,遍历每个数,比如第一个是10,那么count[10]++,第二个是2,count[2]++,依此类推。这样统计结束后,count数组中各个位置的值就是对应的工龄出现的次数。

然后,遍历count数组,从0到50,对于每个i,如果count[i] > 0,就输出i << ":" << count[i] << endl。

这样就能得到正确的结果。

那现在需要考虑的是,如何处理输入中的数字?比如,输入可能有多个空格分隔的数字,可以用cin逐个读取。因为n的值可能很大,但每个工龄都是整数,所以用int类型存储足够。

那代码的大致结构应该是:

- 读取n。

- 初始化count数组为0。

- 循环n次,读取每个工龄,然后count[工龄]++。

- 遍历count数组,输出非零的项。

这样实现的话,非常简洁高效。

那测试一下样例输入是否正确。比如输入样例中的工龄是10、2、0、5、7、2、5、2。统计后:

count[0] =1,count[2]=3,count[5]=2,count[7]=1,count[10]=1。其他如1、3、4等的count都是0,所以不输出。按顺序遍历时,0到10中,这些非零的位置会被正确输出。

那这样应该就能解决问题了。而且无论n有多大,只要工龄范围固定,这个方法都是线性的时间,不会有性能问题。比如当n是1e5的时候,这个方法依然很快。

那代码实现的话,需要注意数组的大小。因为工龄可以到50,所以数组大小应该是51,索引从0到50。例如,工龄50对应count[50]。

另外,在C++中,数组初始化的时候,可以用int count[51] = {0}; 这样所有元素都会被初始化为0。

然后,读取每个数的时候,可能需要注意输入的数值是否在0到50之间。但题目中已经说明输入的工龄范围在[0,50],所以不需要处理越界的情况,可以放心读取。

综上,这个思路应该是正确的。现在把这个思路转化为C++代码。

代码步骤:

1. 关闭同步,加速输入输出。

2. 读取n。

3. 创建count数组,初始化为0。

4. 循环n次,读取每个数x,count[x]++。

5. 遍历count数组,输出非零的元素。

那代码的大概样子是:

#include <iostream>

using namespace std;

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int n;

cin >> n;

int count[51] = {0}; // 初始化为0

for (int i = 0; i < n; ++i) {

int x;

cin >> x;

count[x]++;

}

for (int i = 0; i <= 50; ++i) {

if (count[i] > 0) {

cout << i << ":" << count[i] << "\n";

}

}

return 0;

}

这样应该就可以了。测试一下样例输入:

输入是8,然后是8个数。按照代码处理之后,count数组中的正确位置会被统计。然后遍历输出,符合条件的结果就会被正确打印。

需要注意的是,输出的时候,每个输出项占一行,格式是“工龄:人数”。比如0:1,后面换行。

在代码中,使用cout << i << ":" << count[i] << "\n"; 是正确的。而使用endl的话,可能会因为频繁的刷新缓冲区而变慢,所以使用\n更高效。这里因为已经关闭了同步,所以用\n应该没问题。

所以,这个代码应该可以正确解决问题,并且高效处理所有测试数据,包括最大的n=1e5的情况。比如,对于数据6、7、8、9的情况,这个方法的时间复杂度都是O(n),所以不会有问题。

方法思路

本题要求统计员工工龄的出现次数并按工龄升序输出。由于工龄范围固定(0~50),采用计数排序思想最为高效。具体步骤如下:

  1. 计数统计:创建一个大小为51的数组,遍历输入数据,统计每个工龄出现的次数。

  2. 结果输出:遍历计数数组,输出非零的工龄及其出现次数。

代码实现 

#include <iostream>
using namespace std;

int main() {
    // 关闭同步,加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int count[51] = {0}; // 初始化工龄计数器数组,范围0~50
    
    // 读取每个工龄并更新计数器
    for (int i = 0; i < n; ++i) {
        int age;
        cin >> age;
        count[age]++;
    }
    
    // 按工龄递增顺序输出结果
    for (int i = 0; i <= 50; ++i) {
        if (count[i] > 0) {
            cout << i << ":" << count[i] << "\n";
        }
    }
    
    return 0;
}

代码解释

  1. 输入输出优化

    • ios::sync_with_stdio(false); 和 cin.tie(nullptr); 用于关闭C++标准流与C标准流的同步,显著提升输入输出速度。

  2. 计数统计

    • 定义数组 count[51] 并初始化为0,用于记录0~50岁工龄的出现次数。

    • 循环读取每个员工的工龄,并在对应的 count 数组位置加1。

  3. 结果输出

    • 遍历 count 数组,仅输出出现次数大于0的工龄及其人数,格式为“工龄:人数”。

    • 使用 "\n" 代替 endl 以提高输出效率,避免频繁刷新缓冲区。

此方法时间复杂度为 O(n),适用于大数据量,能够高效处理题目中的各种测试情况。

 


http://www.kler.cn/a/588400.html

相关文章:

  • 【算法】动态规划
  • 3个 Vue nextTick 原理的关键点
  • (七)Spring Boot学习——Redis使用
  • Windows 注册表、定时任务与开机自启
  • 基于有限状态机的数字电路设计:Verilog 实践与探索
  • 柯南ED35 Hello Mr. My Yesterday日文歌词附假名注音,祭奠逝去的青春
  • 如何向 Linux 中加入一个 IO 扩展芯片
  • 4060ti-16G显卡部署deepseek-32B(支持联网搜索)
  • Android Room 框架表现层源码深度剖析(三)
  • Spring MVC 核心组件详解
  • Go语言进化之旅:从1.18到1.24的语法变革
  • 【SpringMVC】常用注解:@MatrixVariable
  • Spark sql 中row的用法
  • 深度学习 Deep Learning 第3章 概率论与信息论
  • 【C++初阶】模板初阶
  • C++内存管理(复习)
  • 游戏成瘾与学习动力激发策略研究——了解“情感解离”“创伤理论”
  • OpenHarmony项目的应用在DevEco Studio配置项目中固定的一键签名
  • android ConstraintLayout布局 实战:打造复杂界面的最佳实践
  • 网络规划设计师软考个人学习资料分享