CSP-J 2019 第一轮 第 42 题：双关键字计数排序：④处应填

题目

2.（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 $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 < n; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++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;
}

④处应填（）

选项

• 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]

答案

A

题解

选 A： ``cpp res[--cnt[a[ord[i]]]] = ord[i]; ``

这行代码可以拆成三步理解：

1. 取原编号：ord[i] 表示按第二关键字 b 排序后，第 i 个元素在原数组中的编号。
2. 取第一关键字：这一对数是 (a[ord[i]], b[ord[i]])，本轮按第一关键字排序，所以用 a[ord[i]]。
3. 确定位置并存编号：前缀和 cnt[x] 表示第一关键字不超过 x 的元素数量，因此 --cnt[x] 是当前元素应放的位置；res 存储原编号，所以右边是 ord[i]。

为什么要倒序遍历？ 因为 --cnt[x] 从相同关键字对应区间的末尾开始放元素。倒序取、从后往前放，可以保持第一关键字相同的元素之间原有的顺序，也就是已经排好的第二关键字顺序。这叫作稳定排序。

其余选项中，B、C 使用了第二关键字；D 的 a[i] 没有通过 ord[i] 找到当前元素的第一关键字。