③处应填()
(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序。将n对10000以内的整数,从小到大排序。 例如有三对整数(3,4)、(2,4)、(3,3),那么排序之后应该是(2,4)、(3,3)、(3,4)。 输入第一行为m,接下来n行,每行有两个数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 = 1000000;
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("%u%u", &a[i], &b[i]);
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
第一处// 利用 cnt 数组统计数量
for (int j = 0; j < maxs; ++j)
cnt[j + 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. ++cnt[b[i]]
B. ++cnt[a[i] * maxs + b[i]]
C. ++cnt[a[i]]
D. ++cnt[i]