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),采用计数排序思想最为高效。具体步骤如下:
-
计数统计:创建一个大小为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
以提高输出效率,避免频繁刷新缓冲区。
-
此方法时间复杂度为 O(n),适用于大数据量,能够高效处理题目中的各种测试情况。