九度oj 题目1374：所有员工年龄排序
生活随笔
收集整理的這篇文章主要介紹了
九度oj 题目1374：所有员工年龄排序
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目描述： 輸入： 輸出： 樣例輸入： 5
43 24 12 57 45
樣例輸出： 12 24 43 45 57
開始沒多想，直接快排 1 #include <cstdio> 2 #include <algorithm> 3 4 int cmp(const void *a, const void *b) { 5 int at = *(int *)a; 6 int bt = *(int *)b; 7 return at > bt; 8 } 9 10 int num[1000002]; 11 int n; 12 13 int main(int argc, char const *argv[]) 14 { 15 while(scanf("%d",&n) != EOF) { 16 for(int i = 0; i < n; i++) { 17 scanf("%d",&num[i]); 18 } 19 qsort(num, n, sizeof(int), cmp); 20 for(int i = 0; i < n; i++) { 21 printf("%d ",num[i]); 22 } 23 puts(""); 24 } 25 return 0; 26 }
公司現(xiàn)在要對所有員工的年齡進(jìn)行排序，因為公司員工的人數(shù)非常多，所以要求排序算法的效率要非常高，你能寫出這樣的程序嗎？
?
輸入可能包含多個測試樣例，對于每個測試案例，
輸入的第一行為一個整數(shù)n(1<= n<=1000000)：代表公司內(nèi)員工的人數(shù)。
輸入的第二行包括n個整數(shù)：代表公司內(nèi)每個員工的年齡。其中，員工年齡age的取值范圍為(1<=age<=99)。
?
對應(yīng)每個測試案例，
請輸出排序后的n個員工的年齡，每個年齡后面有一個空格。
?
開始沒多想，直接快排 1 #include <cstdio> 2 #include <algorithm> 3 4 int cmp(const void *a, const void *b) { 5 int at = *(int *)a; 6 int bt = *(int *)b; 7 return at > bt; 8 } 9 10 int num[1000002]; 11 int n; 12 13 int main(int argc, char const *argv[]) 14 { 15 while(scanf("%d",&n) != EOF) { 16 for(int i = 0; i < n; i++) { 17 scanf("%d",&num[i]); 18 } 19 qsort(num, n, sizeof(int), cmp); 20 for(int i = 0; i < n; i++) { 21 printf("%d ",num[i]); 22 } 23 puts(""); 24 } 25 return 0; 26 }
超時
立馬改成堆排序
1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 using namespace std; 5 6 int n; 7 8 priority_queue <int, vector<int>,greater<int> >que; 9 int main(int argc, char const *argv[]) 10 { 11 while(scanf("%d",&n) != EOF) { 12 for(int i = 0; i < n; i++) { 13 int tmp; 14 scanf("%d",&tmp); 15 que.push(tmp); 16 } 17 while(!que.empty()) { 18 int t = que.top();que.pop(); 19 printf("%d ",t); 20 } 21 puts(""); 22 } 23 return 0; 24 }居然還超時
仔細(xì)看了看題，改成桶排序
1 #include <cstdio> 2 #include <cstring> 3 int n; 4 int age[100]; 5 6 int main(int argc, char const *argv[]) 7 { 8 while(scanf("%d",&n) != EOF) { 9 memset(age, 0, sizeof(age)); 10 while(n--){ 11 int tmp; 12 scanf("%d",&tmp); 13 age[tmp]++; 14 } 15 for(int i = 1; i <= 99; i++) { 16 for(int j = 0; j < age[i];j++) { 17 printf("%d ",i); 18 } 19 } 20 puts(""); 21 } 22 return 0; 23 }再優(yōu)化一下
1 #include <cstdio> 2 #include <cstring> 3 int n; 4 int age[100] = {0}; 5 6 int main(int argc, char const *argv[]) 7 { 8 while(scanf("%d",&n) != EOF) { 9 while(n--){ 10 int tmp; 11 scanf("%d",&tmp); 12 age[tmp]++; 13 } 14 for(int i = 1; i <= 99; i++) { 15 while(age[i]) { 16 printf("%d ",i); 17 age[i]--; 18 } 19 } 20 puts(""); 21 } 22 return 0; 23 }?
轉(zhuǎn)載于:https://www.cnblogs.com/jasonJie/p/5810902.html
總結(jié)
以上是生活随笔為你收集整理的九度oj 题目1374：所有员工年龄排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 初识boost之boost::share
- 下一篇： 动画--过渡属性 transition-