「UVA11462」 年龄排序 题解

题目描述 ​

你被给予年龄(以年)的所有人的一个国家至少1岁。你知道在那个国家没有人能活到100岁以上。 现在，你的任务很简单将所有年龄按升序排序

输入格式 输入文件中有多个测试用例。每一种情况都以整数n(0≤n≤2000000),表示人口总数。 在接下来的几行中，有n个整数表示年龄。 在n = 0的情况下,表示输入已完成,这个案子不应该被起诉。 输出格式 对于每种情况，打印一行，其中包含n个空格分隔的整数。这些整数是那个国家的年龄按升序排序

输入样例 5 3 4 2 1 5 5 2 3 2 3 1 0 输出样例 1 2 3 4 5 1 2 2 3 3

题解思路 ​

通过计数排序完成输出。 由于本题输出要求较严格,不允许有多余的空格

对每组数据计数前都需要将cnt初始化为0

书中提示:“本题中的fill_n函数比memset更方便,性能更好” fill函数的作用是：将一个区间的元素都赋予val值。 函数参数：fill(vec.begin(), vec.end(), val); val为将要替换的值；

fill_n函数的作用是：参数包括 : 一个迭代器，一个计数器（元素个数）以及一个值。 该函数从迭代器指向的元素开始，将指定数量的元素设置为给定的值。

代码 ​

#include <bits/stdc++.h>
using namespace std;

const int N = 2000010;

int n;
int cnt[N];

int main()
{
	while(cin >> n && n)  //如果n为0则退出控制台输入
	{
		bool flag = 0;
		memset(cnt, 0, sizeof cnt); //初始化数组，亦可以用fill_n()
		
		for(int i = 0, x; i < n; i++)	
		{
			cin >> x;
			cnt[x]++;	
		}
		
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < cnt[i]; j++)
				if(!flag)
				{
					cout << i;
					flag = 1;
				} 
				else cout << ' ' << i;
		}	
		cout << endl;
	}
	return 0;
}