排序算法

排序的基本概念；冒泡排序；选择排序；插入排序；计数排序。

概念

排序把元素按关键字 rearrange 成非降或非增序列。CSP-J 要求掌握冒泡、选择、插入的思想与实现，以及值域较小时 计数排序（桶/频次数组）的 O(n+w) 思路；还要知道稳定性、比较次数量级等基本概念。本叶子考「排序算法本身」，与 cspj.algo.greedy 里「先排序再贪心」不同——后者主考点是贪心正确性。与 cspj.cpp.stl 区分：STL 的 sort 是工具调用，这里要能手写 trace 或完善程序空位。初赛 120 分钟里，完善程序常给一段不完整排序代码，问某轮后数组形态或空位填比较符号。

CSP-J 常考

cspj-r1-2019 第 39–43 题：完善程序整段，冒泡或选择排序的多处空位。
cspj-r1-2020 第 5 题：单选题，排序稳定性或算法名称。
cspj-r1-2025 第 12 题：单选题，排序概念或某算法特征。
cspj-r2-2020 第 2 题：复赛编程，成绩值域 0–600，用计数/桶找第 k 大分数线。
cspj-r2-2021 第 2 题：复赛编程，题面给定插入排序伪代码，类型 2 询问原下标在该算法下的最终排位。

// 计数排序：值域 [0, W]
int cnt[601];
for (int i = 0; i < n; ++i) ++cnt[a[i]];
for (int v = 600; v >= 0; --v)
    for (int k = 0; k < cnt[v]; ++k)
        /* 第 k 大的数就是 v */;

易错点

冒泡内层边界 j < n-1-i 写成 n-i，多比较或越界。
选择排序每轮找最小下标后交换，完善程序若交换写在内层循环里会导致结果错。
计数排序忘记值域上界或把下标当成绩本身，阅读程序 trace 时要对照 cnt 数组含义。

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

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;
}

程序

#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\n", ⑤); return 0;}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 30 行
原卷作 printf("%d %d\n", ⑤); ，常规写法应为 printf("%d %d\n", ⑤);
洛谷抓取件为 printf("%d %d", ⑤);；pages/pg-09.png 第 30 行含 \n，已恢复。
已按官方原件恢复：现为原卷原文

39（①）单选空位 ①3 分
①处应填（）

A
++cnt[i]

B
++cnt[b[i]]

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

D
++cnt[a[i]]

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

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;
}

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 30 行
原卷作 printf("%d %d\n", ⑤); ，常规写法应为 printf("%d %d\n", ⑤);
洛谷抓取件为 printf("%d %d", ⑤);；pages/pg-09.png 第 30 行含 \n，已恢复。
已按官方原件恢复：现为原卷原文

40（②）单选空位 ②3 分
②处应填（）

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 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

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;
}

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 30 行
原卷作 printf("%d %d\n", ⑤); ，常规写法应为 printf("%d %d\n", ⑤);
洛谷抓取件为 printf("%d %d", ⑤);；pages/pg-09.png 第 30 行含 \n，已恢复。
已按官方原件恢复：现为原卷原文

41（③）单选空位 ③3 分
③处应填（）

A
++cnt[b[i]]

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

C
++cnt[a[i]]

D
++cnt[i]

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

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;
}

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 30 行
原卷作 printf("%d %d\n", ⑤); ，常规写法应为 printf("%d %d\n", ⑤);
洛谷抓取件为 printf("%d %d", ⑤);；pages/pg-09.png 第 30 行含 \n，已恢复。
已按官方原件恢复：现为原卷原文

42（④）单选空位 ④3 分
④处应填（）

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]

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

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;
}

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 30 行
原卷作 printf("%d %d\n", ⑤); ，常规写法应为 printf("%d %d\n", ⑤);
洛谷抓取件为 printf("%d %d", ⑤);；pages/pg-09.png 第 30 行含 \n，已恢复。
已按官方原件恢复：现为原卷原文

43（⑤）单选空位 ⑤3 分
⑤处应填（）

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

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3.     k ← FLAG -1
   4.     FLAG ← 1
   5.     for j=1 to k do
   6.         if L(j) > L(j+1) then do
   7.              L(j)  ↔ L(j+1)
   8.              FLAG ← j

对 $n$ 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（）。

$n^2$

$n-2$

$n-1$

$n$

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$ 。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （ $1\le n \le 5000,1\le m \le 10^9$ ）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （ $0\le a_i,b_i \le m$ ）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      if (①)
      {
        segment t = A[j];
        ②
      }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> A[i].a >> A[i].b;
  sort();
  int p = 1;
  for (int i = 1; i < n; i++)
    if (③)
      A[p++] = A[i];
  n = p;
  int ans = 0, r = 0;
  int q = 0;
  while (r < m)
  {
    while (④)
      q++;
    ⑤;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

程序

#include <iostream>using namespace std;const int MAXN = 5000;int n, m;struct segment { int a, b; } A[MAXN];void sort() // 排序{ for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) if (①) { segment t = A[j]; ② }}int main(){ cin >> n >> m; for (int i = 0; i < n; i++) cin >> A[i].a >> A[i].b; sort(); int p = 1; for (int i = 1; i < n; i++) if (③) A[p++] = A[i]; n = p; int ans = 0, r = 0; int q = 0; while (r < m) { while (④) q++; ⑤; ans++; } cout << ans << endl; return 0;}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 24 行
原卷作 cin >> A[i].a >> A[i].b; ，常规写法应为 cin >> A[i].a >> A[i].b;
洛谷抓取件为 A[i]・b（中点 U+30FB）；pages/pg-09.png 第 24 行为 .b。另去除洛谷多余行首缩进、ans=0 空格按图像统一。
已按官方原件恢复：现为原卷原文

39（①）单选空位 ①3 分
①处应填（）

A
A[j].b>A[j-1].b

B
A[j].a<A[j-1].a

C
A[j].a>A[j-1].a

D
A[j].b<A[j-1].b

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

输入第一行包含两个整数 $n$ 和 $m$ （ $1\le n \le 5000,1\le m \le 10^9$ ）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （ $0\le a_i,b_i \le m$ ）。

提示：使用贪心法解决这个问题。先用 $O(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
      if (①)
      {
        segment t = A[j];
        ②
      }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> A[i].a >> A[i].b;
  sort();
  int p = 1;
  for (int i = 1; i < n; i++)
    if (③)
      A[p++] = A[i];
  n = p;
  int ans = 0, r = 0;
  int q = 0;
  while (r < m)
  {
    while (④)
      q++;
    ⑤;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

程序

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它程序 · 第 24 行
原卷作 cin >> A[i].a >> A[i].b; ，常规写法应为 cin >> A[i].a >> A[i].b;
洛谷抓取件为 A[i]・b（中点 U+30FB）；pages/pg-09.png 第 24 行为 .b。另去除洛谷多余行首缩进、ans=0 空格按图像统一。
已按官方原件恢复：现为原卷原文

40（②）单选空位 ②3 分
②处应填（）

A
A[j+1]=A[j];A[j]=t;

B
A[j-1]=A[j];A[j]=t;

C
A[j]=A[j+1];A[j+1]=t;

D
A[j]=A[j-1];A[j-1]=t;

编程题

直播获奖

C++时间 1 s内存 256 MB 文件 IO：live.in → live.out

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$ ，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p \times w \%\rfloor)$ ，其中 $w$ 是获奖百分比， $\lfloor x \rfloor$ 表示对 $x$ 向下取整， $\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

输入格式

从文件 live.in 中读入数据。

第一行有两个正整数 $n, w$ ，分别表示选手总数与获奖率。

第二行有 $n$ 个非负整数，依次表示逐一评出的选手成绩。

输出格式

输出到文件 live.out 中。

输出一行 $n$ 个非负整数，依次表示选手成绩逐一评出后，即时的获奖分数线。相邻两个整数之间用一个空格分隔。

样例

输入 1

10 60
200 300 400 500 600 600 0 300 200 100

输出 1

200 300 400 400 400 500 400 400 300 300

设已评测选手人数为 $p$ ，计划获奖人数为 $\max(1, \lfloor p \times w\% \rfloor)$ 。

已评测选手人数 $p$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
计划获奖人数	$1$	$1$	$1$	$2$	$3$	$3$	$4$	$4$	$5$	$6$

已评测选手的分数从高到低排列（分数线用粗体标出）：

$p$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
分数	200	300, 200	400, 300, 200	500, 400, 300, 200	600, 500, 400, 300, 200	600, 600, 500, 400, 300, 200	600, 600, 500, 400, 300, 200, 0	600, 600, 500, 400, 300, 300, 200, 0	600, 600, 500, 400, 300, 300, 200, 200, 0	600, 600, 500, 500, 400, 300, 300, 200, 100, 0

注意，在第 $9$ 名选手的成绩评出之后，计划获奖人数为 $5$ 人，但由于有并列，因此实际会有 $6$ 人获奖。

输入 2

10 30
100 100 600 100 100 100 100 100 100 100

输出 2

100 100 600 600 600 600 100 100 100 100

数据范围

各测试点的 $n$ 如下表：

测试点编号	$n=$
$1 \sim 3$	$10$
$4 \sim 6$	$500$
$7 \sim 10$	$2000$
$11 \sim 17$	$10000$
$18 \sim 20$	$100000$

对于所有测试点，每个选手的成绩均为不超过 $600$ 的非负整数，获奖百分比 $w$ 是一个正整数且 $1 \le w \le 99$ 。

在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float 、double，Pascal 中的 real 、double 、extended 等）存储获奖比例 $w\%$ ，则计算 $5 \times 60\%$ 时的结果可能为 $3.000001$ ，也可能为 $2.999999$ ，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。

部分分

15 分
测试点 $1 \sim 3$ ： $n = 10$ 。
15 分
测试点 $4 \sim 6$ ： $n = 500$ 。
20 分
测试点 $7 \sim 10$ ： $n = 2000$ 。
35 分
测试点 $11 \sim 17$ ： $n = 10000$ 。
15 分
测试点 $18 \sim 20$ ： $n = 100000$ 。

原文保真说明：原卷印刷错误 2 处（照原卷保留，未作修改）

原卷印刷如此其它数据范围
原卷作 | $11 \sim 17$ | $10000$ |
原卷 pg-04 测试点表 n 上界印作 10000（非 10^4 写法），照录。
原卷印刷如此其它数据范围
原卷作 | $18 \sim 20$ | $100000$ |
原卷 pg-04 测试点表 n 上界印作 100000（非 10^5 写法），照录。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（ 2 ）（矩形计数） 平面上有 $n$ 个关键点，求有多少个四条边都和 $x$ 轴或者 $y$ 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

程序

#include <iostream>using namespace std;struct point { int x, y, id;};bool equals(point a, point b) { return a.x == b.x && a.y == b.y;}bool cmp(point a, point b) { return ①;}void sort(point A[], int n) { for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) if (cmp(A[j], A[j - 1])) { point t = A[j]; A[j] = A[j - 1]; A[j - 1] = t; }}int unique(point A[], int n) { int t = 0; for (int i = 0; i < n; i++) if (②) A[t++] = A[i]; return t;}bool binary_search(point A[], int n, int x, int y) { point p; p.x = x; p.y = y; p.id = n; int a = 0, b = n - 1; while (a < b) { int mid = ③; if (④) a = mid + 1; else b = mid; } return equals(A[a], p);}const int MAXN = 1000;point A[MAXN];int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> A[i].x >> A[i].y; A[i].id = i; } sort(A, n); n = unique(A, n); int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) { ans++; } cout << ans << endl; return 0;}

39（①）单选空位 ①3 分
①处应填 ( )

A
a.x != b.x ? a.x < b.x : a.id < b.id

B
a.x != b.x ? a.x < b.x : a.y < b.y

C
equals(a, b) ? a.id < b.id : a.x < b.x

D
equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

编程题

插入排序

C++时间 1 s内存 512 MB 文件 IO：sort.in → sort.out

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$ ，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i <= n; i++)
    for (int j = i; j >= 2; j--)
        if ( a[j] < a[j-1] ){
            int t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }

这下面是 Pascal 的示范代码：

for i:=1 to n do
    for j:=i downto 2 do
        if a[j]<a[j-1] then
            begin
                t:=a[j];
                a[j]:=a[j-1];
                a[j-1]:=t;
            end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$ ，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1~x~v$ ：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$ 。保证 $1 \le x \le n$ ， $1 \le v \le 10^9$ 。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

$2~x$ ：这是第二种操作，假设 H 老师按照上面的伪代码对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$ ，在排序后的新数组所处的位置。保证 $1 \le x \le n$ 。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$ 。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

输入格式

从文件 sort.in 中读入数据。

第一行，包含两个正整数 $n, Q$ ，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$ 。

接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。

输出格式

输出到文件 sort.out 中。

对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。

样例

输入 1

输出 1

1
1
2

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 2, 1$ 。

在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 1, 2$ 。

注意虽然此时 $a_2 = a_3$ ，但是我们不能将其视为相同的元素。

数据范围

对于所有测试数据，满足 $1 \le n \le 8000$ ， $1 \le Q \le 2 \times 10^5$ ， $1 \le x \le n$ ， $1 \le v, a_i \le 10^9$ 。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

测试点	$n \le$	$Q \le$	特殊性质
$1 \sim 4$	$10$	$10$	无
$5 \sim 9$	$300$	$300$	无
$10 \sim 13$	$1500$	$1500$	无
$14 \sim 16$	$8000$	$8000$	保证所有输入的 $a_i, v$ 互不相同
$17 \sim 19$	$8000$	$8000$	无
$20 \sim 22$	$8000$	$2 \times 10^5$	保证所有输入的 $a_i, v$ 互不相同
$23 \sim 25$	$8000$	$2 \times 10^5$	无

部分分

16 分
测试点 $1 \sim 4$ ： $n \le 10$ ， $Q \le 10$ ，无特殊性质。
20 分
测试点 $5 \sim 9$ ： $n \le 300$ ， $Q \le 300$ ，无特殊性质。
16 分
测试点 $10 \sim 13$ ： $n \le 1500$ ， $Q \le 1500$ ，无特殊性质。
12 分
测试点 $14 \sim 16$ ： $n \le 8000$ ， $Q \le 8000$ ，保证所有输入的 $a_i, v$ 互不相同。
12 分
测试点 $17 \sim 19$ ： $n \le 8000$ ， $Q \le 8000$ ，无特殊性质。
12 分
测试点 $20 \sim 22$ ： $n \le 8000$ ， $Q \le 2 \times 10^5$ ，保证所有输入的 $a_i, v$ 互不相同。
12 分
测试点 $23 \sim 25$ ： $n \le 8000$ ， $Q \le 2 \times 10^5$ ，无特殊性质。

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它题面描述
原卷作 t:=a[j]; a[j]:=a[j-1]; a[j-1]:=t; ，常规写法应为 t:=a[i]; a[i]:=a[j]; a[j]:=t;
洛谷 P7910 Pascal 示范代码误写为 `a[i]` 交换；扫描件 pg-06 为 `a[j]` / `a[j-1]` 交换，已按图像恢复。
已按官方原件恢复：现为原卷原文

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

以下排序算法的常见实现中，哪个选项的说法是错误的：（）。

冒泡排序算法是稳定的

简单选择排序是稳定的

简单插入排序是稳定的

归并排序算法是稳定的

某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序，请问需要进行多少次元素交换？

$5$

$6$

$7$

$8$