【題目】

CSP-J 2019 入門級 第一輪（初賽） 完善程序（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. ①處應填（）
   A. ++cnt[i]
   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]]]

【題目考點】

1. 索引排序

2. 計數排序

3. 排序的穩定性

4. 前綴和

【解題思路】

對數對進行排序，目標順序為：先按第一個數字從小到大排序，如果第一個數字相同，再按第二數字從小到大排序。
如果使用穩定的排序算法，則可以先按第二個數字從小到大對所有數對排序，此時數對序列的順序已經滿足第二個數字是升序的。再按照第一個數字從小到大排序，如果第一個數字相同，由于使用的是穩定的排序算法，數對的第二個數字會按照其原有的升序順序排列，最終結果就符合了目標順序。
本題使用的是計數排序。

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

題目說了，有n對10000以內的整數，代碼中常量maxs是10000，以maxs為長度的數組cnt應該為計數數組，cnt[i]表示數值i出現的次數。

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 數組統計數量

輸入每個數對$(a_i,b_i)$，先將計數數組cnt每個元素初始化為0。而后要做的就是“利用 cnt 數組統計數量”。題目的提示中說了：“應先對第二關鍵字排序，再對第一關鍵字排序”，也就是應該先根據第二個關鍵字從小到大對各數對進行排序。先對第二個關鍵字進行計數，此時cnt[b[i]]表示第二個關鍵字值為b[i]的數對的數量。第i個數對為$(a_i,b_i)$，那么第二個關鍵字為b[i]的數對的數量應該增加1，即cnt[b[i]]++，第(1)空填cnt[b[i]]++，選B。

	for (int i = 0; i < maxs; ++i) cnt[i + 1] += cnt[i];for (int i = 0; i < n; ++i)②; // 記錄初步排序結果

遍歷執行cnt[i+1] += cnt[i]，cnt數組經過更新后變成了自己的前綴和。
cnt[b[i]]的概念變為第二個關鍵字小于等于b[i]的數對的數量，其中最后一個數對就是從1開始數的第cnt[b[i]]個數對，也就是從0開始數的第cnt[b[i]]-1個數對。
假想按照輸入順序得到原數對序列為$s$，排序后的目標數對序列為$t$，由于原序列$s$和目標序列$t$都是下標從0開始的，此時cnt[b[i]]-1也就是所有第二個關鍵字小于等于b[i]的數對按照第二個關鍵字升序排序后最后一個數對的下標，也就是第二個關鍵字等于b[i]的最后一個數對的下標。
目標序列$t$的第i個（下標i位置）的元素$t[i]$在原序列中$s$的下標為ord[i]，也就是滿足$t[i]=s[ord[i]]$，ord數組即為索引數組。
看原序列$s$的第i數對$s[i]$，其第二個關鍵字為b[i]。第二個關鍵字為b[i]的所有數對在目標序列中最后一個數對的下標為cnt[b[i]]-1，先讓cnt[b[i]]減少1，即--cnt[b[i]]。將當前第i數對$s[i]$放在目標序列$t$下標cnt[b[i]]位置，也就是$t[cnt[b[i]]]=s[i]$，那么目標序列第cnt[b[i]]元素在原序列中的下標為i，因此設ord[cnt[b[i]]] = i。
cnt[b[i]]減少1后，下一個第二個關鍵字為$b_i$的數對在目標序列中的最后一個元素的下標就是cnt[b[i]]-1。可以重復上述過程，求出該數對在排序后的下標。因此第(2)空填ord[--cnt[b[i]]] = i，選D。

看一個使用上述過程進行計數排序的例子：原序列a為1 2 1 2 1
遍歷計數，得cnt[1]:3, cnt[2]:2
cnt變為自己的前綴和后，cnt[1]:3, cnt[2]:5
排序后的目標序列為t序列，ord[i]是t[i]在a序列中的下標。
遍歷a序列，a[0]為1，最后一個1應該放在cnt[1]-1=2位置，所以先--cnt[1]，cnt[1]變為2，而后t[cnt[1]]=1，ord[cnt[a[0]]]=ord[2]=0。。
a[1]為2，最后一個2應該放在cnt[2]-1=4位置，所以先--cnt[2]，而后t[cnt[2]]=2，ord[cnt[a[1]]]=ord[4]=1
a[2]為1，最后一個1應該放在cnt[1]-1=1位置，所以先--cnt[1] ，cnt[1]變為1，而后t[cnt[1]]=1，ord[cnt[a[2]]]=ord[1]=2
依此類推，填表后結果為：

下標	0	1	2	3	4
t	a[4]:1	a[2]:1	a[0]:1	a[3]:2	a[1]:2
ord	4	2	0	3	1

i從0到n-1循環，重復上述過程，即可求出ord數組，得到了每個在目標序列中的數值在原序列中的下標，也就是求出了按照第二個關鍵字$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];

接下來要對根據第二關鍵字排序后的序列再根據第一關鍵字排序。
此時應該對a[i]進行計數，cnt[a[i]]此時表示a[i]出現的次數。第(3)空填++cnt[a[i]]，選C。
而后又是cnt[i+1] += cnt[i]操作將cnt變為自己的前綴和。此時cnt[a[i]]為第一個關鍵字小于等于a[i]的數對的數量。序列下標從0開始，按第一個關鍵字排序后下標cnt[a[i]]-1位置就是第一個關鍵字為a[i]的最后一個數對的下標。

 	for (int i = n - 1; i >= 0; --i)④ // 記錄最終排序結果for (int i = 0; i < n; i++)printf("%d %d", ⑤);return 0;
}

經過第一趟按照第二個關鍵字排序后得到數對序列$t$，現在對$t$序列進行遍歷，按照第一個關鍵字進行計數排序，排序后的目標序列$u$。目標序列$u$中第i元素$u[i]$在原序列$s$中的下標為res[i]，即$u[i]=s[res[i]]$，res也是索引數組。
其中$t[i]$的第一個關鍵字記為$t[i].a=s[ord[i]].a$，就是a[ord[i]]。第二個關鍵字記為$t[i].b=s[ord[i]].b$，就是b[ord[i]]。
遍歷$t$序列，訪問到第i個數對$t[i]$，其第一個關鍵字為$t[i].a$，第一個關鍵字為$t[i].a$的最后一個數對在目標序列中$u$的下標為$cnt[t[i].a]?1$。
先將$cnt[t[i].a]$減少1，而后可以設$u[cnt[t[i].a]]=t[i]$
已知$t[i]=s[ord[i]]$，那么$u[cnt[t[i].a]]=s[ord[i]]$
根據res的定義，有$res[cnt[t[i].a]]=ord[i]$
已知$t[i].a$就是a[ord[i]]，那么有res[cnt[a[ord[i]]]]=ord[i]
整合上面將$cnt[t[i].a]$減1的過程，實際需要執行的語句為res[--cnt[a[ord[i]]]] = ord[i]，第(4)空選A。
$cnt[t[i].a]$減少1后，下一次遇到第一個關鍵字為$t[i].a$的數對，該數對應該在目標序列$u$的下標$cnt[t[i].a]?1$位置，可以重復上述過程。
為了滿足排序的穩定性，第一個關鍵字相同時第二個關鍵字從小到大排列。當前算法對于每個第一個關鍵字相同的數對，在目標序列中都是從后向前賦值的，因此需要按照第二個關鍵字從大到小的順序遍歷，也就是要對$t$序列從后向前遍歷，因此該循環的循環控制變量i是從n-1到0循環的。
最后輸出的是最終序列$u$，$u[i]=s[res[i]]$，因此輸出的數對為a[res[i]],b[res[i]]，第(5)空選B。

【答案】

1. B
2. D
3. C
4. A
5. B