P6329 - 2019 完善程序2：计数排序

内存限制：256 MB 时间限制：2 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

提交提交记录统计 Web Board

(计数排序) 计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。

例如有三对整数(3,4) 、(2,4) 、(3,3) ，那么排序之后应该是

(2,4)、(3,3)、(3,4)。输入第一-行为n,接下来n行，第i行有两个数a[i]和b[i]，分别表示第i对整数的第- - 关键字和第二关键字。

从小到大排序后输出。

数据范围1≤n≤10⁷，1<=a[i],b[i]<=10⁴

提示:应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第

二关键字排序的结果，数组res[]存储双关键字排序的结果。

	#include <cstdio>

	#include <cstring>

	usingnamespacestd;

	constintmaxn = 10000000;

	constintmaxs = 10000;

	 intn;

	unsigned a[maxn], b[maxn], res[maxn], ord[maxn];

	unsigned cnt[maxs + 1];

	intmain() {

	    scanf("%d", &n);

	    for(inti=0;i<n;++i)

	    scanf("%d%d", &a[i], &b[i]);

	    memset(cnt, 0,sizeof(cnt));

	    for(inti=0;i<n;++i)

	       ++cnt [b[i]];//利用cnt数组统计数量

	    for(inti=0;i<maxs;++i)

	        cnt[i + 1] += cnt[i];

	    for(inti=0;i<n;++i)

	       ord[--cnt[b[i] ]] = i;// 记录初步排序结果B. x, y- step

	    memset(cnt, 0,sizeof(cnt));

	    for(inti=0;i<n;++i)

	       ++cnt[a[i]];//利用cnt数组统计数量

	    for(inti=0;i<maxs;++i)

	        cnt[i + 1] += cnt[i];

	    for(inti=n-1;i>=0;--i)

	       res[--cnt[a[ord[i]]]] = ord[i];// 记录最终排序结果

	    for(inti=0;i<n;++i)

	        printf("%d %d\n",  a[res [i]], b[res[i]]);

	    return0;

	}

2019 完善程序2

6329: 2019 完善程序2：计数排序

题目描述

输入格式

输入样例复制

输出样例复制

分类标签