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

题目

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. 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

答案

D

题解

答案选 D：

``cpp ord[--cnt[b[i]]] = i; ``

理解这句代码，抓住两点：

1. 先按第二关键字 b[i] 排序，所以用 cnt[b[i]] 来确定位置。
2. ord[] 保存原数据的下标，所以赋值为 i，方便后续通过 a[ord[i]]、b[ord[i]] 找到这对整数。

统计并求前缀和后，cnt[x] 表示第二关键字 小于等于 x 的元素个数。数组下标从 0 开始，因此 --cnt[b[i]] 就是当前元素应放的位置；同时减一，为下一个同值元素留出位置。

例如原数据为：

``text 下标： 0 1 2 数对：(3,4) (2,4) (3,3) ``

按这句代码处理后，ord = [2, 1, 0]，对应：

``text (3,3)、(2,4)、(3,4) ``

第二关键字已经从小到大排列。之后再对第一关键字做稳定排序，就能得到题目要求的结果。