（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数

排序，将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[]存储双关键字排序的结果。

试补全程序。

1 #include <cstdio>

2 #include <cstring>

3 using namespace std;

4 const int maxn = 10000000;

5 const int maxs = 10000;

6 

7 int n;

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

9 unsigned cnt[maxs + 1];

10 int main() {

11 scanf("%d", &n);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27 ④ // 记录最终排序结果

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

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

30

31 return 0;

32 }

①处应填（）

②处应填（）

③处应填（）

④处应填（）

⑤处应填（）

1.

A. ++cnt [i]

B. ++cnt[b[i]]

C. ++cnt[a[i] * maxs + b[i]]

D. ++cnt[a[i]]

2.

A. ord[--cnt[a[i]]] = i

B. ord[--cnt[b[i]]] = a[i]

C. ord[--cnt[a[i]]] = b[i]

D. ord[--cnt[b[i]]] = i

3.

A. ++cnt[b[i]]

B. ++cnt[a[i] * maxs + b[i]]

C. ++cnt[a[i]]

D. ++cnt [i]

4.

A. res[--cnt[a[ord[i]]]] = ord[i]

B. res[--cnt[b[ord[i]]]] = ord[i]

C. res[--cnt[b[i]]] = ord[i]

D. res[--cnt[a[i]]] = ord[i]

5.

A. a[i], b[i]

B. a[res[i]], b[res[i]]

C. a[ord[res[i]]], b[ord[res[i]]]

D. a[res[ord[i]]], b[res[ord[i]]]

第一空(3分)：_____________________________

第二空(3分)：_____________________________

第三空(3分)：_____________________________

第四空(3分)：_____________________________

第五空(3分)：_____________________________