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

PTA7-13 统计工龄

article 2025/3/17 13:26:33

题目描述

给定公司 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），采用计数排序思想最为高效。具体步骤如下：

计数统计：创建一个大小为51的数组，遍历输入数据，统计每个工龄出现的次数。
结果输出：遍历计数数组，输出非零的工龄及其出现次数。

代码实现

#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;
}

代码解释

输入输出优化：
- ios::sync_with_stdio(false); 和 cin.tie(nullptr); 用于关闭C++标准流与C标准流的同步，显著提升输入输出速度。
计数统计：
- 定义数组 count[51] 并初始化为0，用于记录0~50岁工龄的出现次数。
- 循环读取每个员工的工龄，并在对应的 count 数组位置加1。
结果输出：
- 遍历 count 数组，仅输出出现次数大于0的工龄及其人数，格式为“工龄:人数”。
- 使用 "\n" 代替 endl 以提高输出效率，避免频繁刷新缓冲区。