242
UVA之11462 - Age Sort
【題目】
You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.
Input
There are multiple test cases in the input file. Each case starts with an integer n (0<n<=2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.
Output
For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order.
Warning: Input Data is pretty big (~ 25 MB) so use faster IO.
Sample Input Output for Sample Input
|
5 3 4 2 1 5 5 2 3 2 3 1 0 |
1 2 3 4 5 1 2 2 3 3 |
Note: The memory limit of this problem is 2 Megabyte Only.
Problem Setter: Mohammad Mahmudur Rahman
Special Thanks: Shahriar Manzoor
【分析】
由於數據太大，內存限製太緊（甚至都不能把它們全讀進內存），因此無法使用快速排序方法。但整數範圍很小，可以用計數排序方法。
【代碼】
/*********************************
* 日期：2014-5-2
* 作者：SJF0115
* 題號: 11462 - Age Sort
* 地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
* 來源：UVA
* 結果：Accepted
* 總結：計數排序
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main(){
int i,j,age,n;
int count[101];
//freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
while(scanf("%d",&n)!= EOF && n != 0){
//初始化
memset(count,0,sizeof(count));
//統計人數
for(i = 0;i < n;i++){
scanf("%d",&age);
count[age]++;
}
//按照年齡從小到大輸出
bool first = true;//標誌 控製格式 第一次輸出
for(i = 1;i < 101;i++){
for(j = 0;j < count[i];j++){
if(!first){
printf(" ");
}
first = false;
printf("%d",i);
}
}
printf("\n");
}
return 0;
}
如果還要精益求精，可以優化輸入輸出，進一步降低運行時間。程序如下。
/*********************************
* 日期：2014-5-2
* 作者：SJF0115
* 題號: 11462 - Age Sort
* 地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
* 來源：UVA
* 結果：Accepted
* 總結：
**********************************/
#include<cstdio>
#include<cstring>
#include<cctype> //為了使用isdigit宏
//內聯函數
//逐字符輸入
inline int ReadInt(){
char c = getchar();
while(!isdigit(c)){
c = getchar();
}
int x = 0;
while(isdigit(c)){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
//聲明成全局變量可以減小開銷
int buf[10];
//逐字符輸出
inline void WriteInt(int i){
int p = 0;
//特殊情況：i等於0的時候需要輸出0，而不是什麼也不輸出
if(i == 0){
p++;
}
else{
//分解為字符
while(i){
buf[p++] = i % 10;
i /= 10;
}
}
//逐字符輸出
for(int j = p-1; j >=0; j--){
//逆序輸出
putchar('0' + buf[j]);
}
}
int main() {
int n, x, c[101];
while(n = ReadInt()){
memset(c, 0, sizeof(c));
for(int i = 0; i < n; i++) c[ReadInt()]++;
//輸出
int first = 1;
for(int i = 1; i <= 100; i++){
for(int j = 0; j < c[i]; j++) {
if(!first) putchar(' ');
first = 0;
WriteInt(i);
}
}
putchar('\n');
}//while
return 0;
}
上述優化使得運行時間縮短了約2/3。一般情況下，當輸入輸出數據量很大時，應盡量用scanf和printf函數；如果時間效率還不夠高，應逐字符輸入輸出，就像上麵的readint和writeint函數。不管怎樣，在確信I/O時間成為整個程序性能瓶頸之前，不要盲目優化。測試方法也很簡單：輸入之後不執行主算法，直接輸出一個任意的結果，看看運行時間是否過長。
最後更新：2017-04-03 12:56:30