二十八、 统计工龄
二十八、 統(tǒng)計(jì)工齡
文章目錄
- 二十八、 統(tǒng)計(jì)工齡
- 題目描述
- 解題思路
- 上機(jī)代碼
題目描述
給定公司N名員工的工齡，要求按工齡增序輸出每個(gè)工齡段有多少員工。
輸入格式：
輸入首先給出正整數(shù)N（即員工總?cè)藬?shù)）；隨后給出N個(gè)整數(shù)，即每個(gè)員工的工齡，范圍在[18, 65]。
輸出格式：
按工齡的遞增順序輸出每個(gè)工齡的員工個(gè)數(shù)，格式為：“工齡:人數(shù)”。每項(xiàng)占一行。如果人數(shù)為0則不輸出該項(xiàng)。
| 測(cè)試用例 1 | 8 30 20 20 50 37 21 51 20 | 20:3 21:1 30:1 37:1 50:1 51:1 | 1秒 | 64M | 0 |
解題思路
很簡(jiǎn)單的排序題，數(shù)據(jù)范圍小，數(shù)據(jù)量也很少，任取一種排序方法都能輕松AC。
這里重點(diǎn)補(bǔ)充一種方法：桶排序。這種排序方法并沒(méi)有在教學(xué)大綱中，但認(rèn)真讀過(guò)一些算法書(shū)籍，或者接觸過(guò)ACM的同學(xué)都應(yīng)該知道這種排序方法。
桶排序是一種很快很簡(jiǎn)單的排序方法，在指定區(qū)間 [a,b] 內(nèi)，為每一個(gè)數(shù)都建立一個(gè) “桶”，對(duì)于輸入的待排序數(shù)，屬于哪個(gè) “桶” 就把它裝入哪對(duì)應(yīng)的 “桶”中，最后按照 “桶” 的排列順序依次將數(shù)輸出即可。桶排序的思想很簡(jiǎn)單，是一種典型的用空間換時(shí)間的排序方法。其限制條件也很明顯，對(duì)于空間開(kāi)銷不能太大，空間開(kāi)銷太大的排序不適合用桶排序。
如果題目中指定了數(shù)據(jù)的區(qū)間是【a，b】，我們?cè)趨^(qū)間【a，b】上對(duì)每一個(gè)數(shù)都建立一個(gè) “桶”。對(duì)于輸入數(shù) m（a<= m <=b），就將其裝入編號(hào)為 m 的“桶”中；對(duì)于 n（a<= n <=b），就將 n 裝入編號(hào) n 的 “桶”中。等所有輸入數(shù)都裝填完畢，按照 a 到 b 的順序，依次輸出“桶”中元素即可。（因?yàn)樘钊氲臄?shù)值與 “桶” 的編號(hào)相同，“桶”中有幾個(gè)元素，輸出時(shí)就將 “桶” 的編號(hào)輸出幾次，遇到空 “桶” 則直接跳過(guò)。）
桶的存儲(chǔ)結(jié)構(gòu)也很簡(jiǎn)單，用簡(jiǎn)單的一維數(shù)組就可以。數(shù)組的長(zhǎng)度就是“桶”的個(gè)數(shù)，數(shù)組的類型就是“桶”的最大容量。
比如 int a[100]，“桶”的個(gè)數(shù)為 100，每只“桶”的容量是 32767。
上機(jī)代碼
本題就是典型的指定區(qū)間，很適合使用桶排序來(lái)求解，題目不需要依次輸出元素，僅輸出元素的個(gè)數(shù)就可以了。
#include<cstdio> #include<cstring> #include<cstdlib> using namespace std; //桶排序 int main() {int n, x, c[101];memset(c, 0, sizeof(c));scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d", &x);c[x]++;}for (int i = 18; i <= 65; i++){if(c[i]!=0)printf("%d:%d\n", i, c[i]);}//system("pause");return 0; }總結(jié)
