#cspjc2019w2. 2019csp-j初赛完善程序2

2019csp-j初赛完善程序2

2019csp-j初赛完善程序2

每小题3 分

1.第二题

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

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

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

​ 从小到大排序后输出。

​ 数据范围1<n<107,1<a[i],b[i]<1041<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;
}

1.①处应填( ){{ select(1) }}

  • ++cnt[i]
  • ++cnt[b[i]]
  • ++cnt[a[i] * maxs + b[i]]
  • ++cnt[a[i]]

2.②处应填( ){{ select(2) }}

  • ord[--cnt[a[i]]] = i
  • ord[--cnt[b[i]]] = a[i]
  • ord[--cnt[a[i]]] = b[i]
  • ord[--cnt[b[i]]] = i

3.③处应填( ) {{ select(3) }}

  • ++cnt[b[i]]
  • ++cnt[a[i] * maxs + b[i]]
  • ++cnt[a[i]]
  • ++cnt[i]

4.④处应填( ) {{ select(4) }}

  • res[--cnt[a[ord[i]]]] = ord[i]
  • res[--cnt[b[ord[i]]]] = ord[i]
  • res[--cnt[b[i]]] = ord[i]
  • res[--cnt[a[i]]] = ord[i]

5.⑤处应填( ) {{ select(5) }}

  • a[i], b[i]
  • a[res[i]], b[res[i]]
  • a[ord[res[i]]],b[ord[res[i]]]
  • a[res[ord[i]]],b[res[ord[i]]]