导航菜单

CSP

第39题

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

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

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

数据范围≤n≤107,1≤a[i],b[i]≤104。

提示:应先对第二关键字排序,再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果,数组 res_____ 存储双关键字排序的结果。

试补全程序

#include #include using namespace std;const int maxn = 10000000;const int maxs = 10000;int n;unsigned a[maxn], b[maxn],res[maxn], ord[maxn];unsigned cnt[maxs + 1];int main() {    scanf("%d", &n);    for (int i = 0; i 

相关推荐: