（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将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^7 , 1<a[i],b[i]<10^4$



提示：应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第二关键字排序的结果，数组res[]存储双关键字排序的结果。



试补全程序。

#include <cstdio>


#include <cstring>


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 < n; ++i) 


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


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


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


        ①; // 利用 cnt 数组统计数量


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


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


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


        ②; // 记录初步排序结果


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


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


        ③; // 利用 cnt 数组统计数量


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


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


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


        ④ // 记录最终排序结果


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


        printf("%d %d", ⑤);





    return 0;


}

选择题