题库 信息学奥赛题库 题目列表 计数排序是一个广泛使用的排序方法。下面的程序使用双...
组合题

计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序,将n对10000以内的整数,从小到大排序。

例如有三对整数(3,4)、(2,4)、(3,3),那么排序之后应该是(2,4)、(3,3)、(3,4)。

输入第一行为n,接下来n行,第i行有两个数a[i]和b[i],分别表示第 i对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围1<n<107107,1<a[i],b[i]<104104。


提示:应先对第二关键字排序,再对第一关键字排序。数组ord[ ]存储第二关键字排序的结果,数组res[ ]存储双关键字排序的结果。试补全程序。

##include <bits/stdc++.h>
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)
        ______(1)______; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ______(2)______; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ______(3)______; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ______(4)______ // 记录最终排序结果
            for (int i = 0; i < n; i++)
                printf("%d %d", ______(5)______);
 
    return 0;
}
第1题 单选

①处应填( )

A.

++cnt[1]

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

题目信息
完善程序 2019年 初赛
-
正确率
0
评论
175
点击