参考《算法竞赛进阶指南》、AcWing题库

排序

在程序设计中, 通常会使用到以下这些排序算法, 这里把它们分为三类:

  1. 选择排序、插入排序、冒泡排序
  2. 堆排序、归并排序、快速排序
  3. 计数排序、基数排序、桶排序

前两类是基于比较的排序算法, 对 nn 个元素进行排序时, 若元素比较大小的时间复杂度为 O(1)O(1), 则第一类排序算法的时间复杂度为 O(n2)O\left(n^{2}\right), 第二类排序算法的时间复杂度为 O(nlog⁡n)O(n \log n) 。实际上, 基于比较的排序算法的时间复杂度下界为 O(nlog⁡n)O(n \log n), 因此堆排序、归并排序与快速排序已经是时间复杂度最优的基于比较的排序算法。

第三类算法换了一种思路, 它们不直接比较大小, 而是对被排序的数值采取按位划分、分类映射等处理方式, 其时间复杂度不仅与 nn 有关, 还与数值的大小范围 mm 有关。

离散化

排序算法的第一个应用是离散化。通俗地讲, “离散化” 就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。例如在很多情况下, 问题的范围虽然定义在整数集合 Z\mathbb{Z}, 但是只涉及其中 mm 个有限数值, 并且与数值的绝对大小无关 (只把这些数值作为代表, 或只与它们的相对顺序有关)。此时, 我们就可以把整数集合 Z\mathbb{Z} 中的这 mm 个整数与 1∼m1 \sim m 建立映射关系。如果有一个时间、空间复杂度与数值范围 Z\mathbb{Z} 的大小有关的算法, 在离散化后, 该算法的时间、空间复杂度就降低为与 mm 相关。

具体地说, 假设问题涉及 intint 范围内的 nn 个整数 a[1]∼a[n]a[1] \sim a[n], 这 nn 个整数可能有重复, 去重以后共有 mm 个整数。我们要把每个整数 a[i]a[i] 用一个 1∼m1 \sim m 之间的整数代替, 并且保持大小顺序不变, 即如果 a[i]a[i] 小于 (或等于、大于) a[j]a[j], 那么代替 a[i]a[i] 的整数也小于（或等于、大于) 代替 a[j]a[j] 的整数。

很简单, 我们可以把 aa 数组排序并去掉重复的数值, 得到有序数组 b[1]∼b[m]b[1] \sim b[m], 在 bb 数组的下标 ii 与数值 b[i]b[i] 之间建立映射关系。若要查询整数 i(1≤i≤m)i(1 \leq i \leq m) 代替的数值, 只需直接返回 b[i]b[i]; 若要查询整数 a[j](1≤j≤n)a[j](1 \leq j \leq n) 被哪个 1∼m1 \sim m 之间的整数代替, 只需在数组 bb 中二分查找 a[j]a[j] 的位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
// 离散化
void discrete() {
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) // 也可用STL中的unique函数
		if (i == 1 || a[i] != a[i - 1])
			b[++m] = a[i];
}

// 离散化后，查询x映射为哪个1~m之间的整数
void query(int x) {
	return lower_bound(b + 1, b + m + 1, x) - b;
}

103. 电影

莫斯科正在举办一个大型国际会议，有 nn 个来自不同国家的科学家参会。

每个科学家都只懂得一种语言。

为了方便起见，我们把世界上的所有语言用 11 到 10910^9 之间的整数编号。

在会议结束后，所有的科学家决定一起去看场电影放松一下。

他们去的电影院里一共有 mm 部电影正在上映，每部电影的语音和字幕都采用不同的语言。

对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影，可以让观影很开心的人最多。

如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

输入格式

第一行输入一个整数 nn，代表科学家的数量。

第二行输入 nn 个整数 a1,a2…ana_1,a_2…a_n，其中 aia_i 表示第 ii 个科学家懂得的语言的编号。

第三行输入一个整数 mm，代表电影的数量。

第四行输入 mm 个整数 b1,b2…bmb_1,b_2…b_m，其中 bib_i 表示第 ii 部电影的语音采用的语言的编号。

第五行输入 mm 个整数 c1,c2…cmc_1,c_2…c_m，其中 cic_i 表示第 ii 部电影的字幕采用的语言的编号。

请注意对于同一部电影来说，bi≠cib_i \neq c_i。

同一行内数字用空格隔开。

输出格式

输出一个整数，代表最终选择的电影的编号。电影编号 1∼m1 \sim m。

如果答案不唯一，输出任意一个均可。

数据范围

1≤n,m≤2000001 \le n,m \le 200000,
1≤ai,bi,ci≤1091 \le a_i,b_i,c_i \le 10^9

输入样例：

1
2
3
4
5
3
2 3 2
2
3 2
2 3

输出样例：

1
2

算法分析

虽然语言的范围在 intint 以内, 但是这 mm 部电影与 nn 个人最多涉及 2∗m+n2 * m+n 种语言。我们把所有电影和人涉及的语言放进一个数组, 排序并离散化, 用一个 1∼2∗m+n1 \sim 2 * m+n 之间的整数代替每种语言。此时我们就可以用数组直接统计会上述每种语言的人的数量, 从而选择满足题目要求的电影。时间复杂度为 O((n+m)log⁡(n+m))O((n+m) \log (n+m)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200006;
int n, m, a[N], x[N], y[N], cinema[N*3], tot = 0, k, ans[N*3];

int find(int f) {
	return lower_bound(cinema + 1, cinema + k + 1, f) - cinema;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		cinema[++tot] = a[i];
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &x[i]);
		cinema[++tot] = x[i];
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &y[i]);
		cinema[++tot] = y[i];
	}
	sort(cinema + 1, cinema + tot + 1);
	k = unique(cinema + 1, cinema + tot + 1) - (cinema + 1);
	memset(ans, 0, sizeof(ans));
	for (int i = 1; i <= n; i++) ans[find(a[i])]++;
	int ans0 = 1, ans1 = 0, ans2 = 0;
	for (int i = 1; i <= m; i++) {
		int ansx = ans[find(x[i])], ansy = ans[find(y[i])];
		if (ansx > ans1 || (ansx == ans1 && ansy > ans2)) {
			ans0 = i;
			ans1 = ansx;
			ans2 = ansy;
		}
	}
	cout << ans0 << endl;
	return 0;
}

Solution

中位数

在有序序列中, 中位数具有一些很优美的性质, 可以引出一系列与它相关的问题。动态维护序列的中位数也非常值得探讨。我们通过几道例题来感受中位数的相关应用。

104. 货仓选址

在一条数轴上有 NN 家商店，它们的坐标分别为 A1∼ANA_1 \sim A_N。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 NN。

第二行 NN 个整数 A1∼ANA_1 \sim A_N。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤1000001 \le N \le 100000,
0≤Ai≤400000 \le A_i \le 40000

输入样例：

1
2
4
6 2 9 1

输出样例：

1
12

算法分析

把 A[1]∼A[N]A[1] \sim A[N] 排序, 设货仓建在 XX 坐标处, XX 左侧的商店有 PP 家, 右侧的商店有 QQ 家。若 P<QP<Q, 则每把货仓的选址向右移动 1 单位距离, 距离之和就会变小 Q−Q- PP 。同理, 若 P>QP>Q, 则货仓的选址向左移动会使距离之和变小。当 P=QP=Q 时为最优解。

因此货仓应该建在中位数处, 即把 AA 排序后, 当 NN 为奇数时, 货仓建在 A[(N+1)/2]A[(N+1)/2] 处最优；当 NN 为偶数时，货仓建在 A[N/2]∼A[N/2+1]A[N/2] \sim A[N/2+1] 之间的任何位置都是最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 100006;
int n, a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	ll ans = 0;
	for (int i = 1; i <= n / 2; i++)
		ans += a[n-i+1] - a[i];
	cout << ans << endl;
	return 0;
}

Solution

105. 七夕祭

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由 NN 排 MM 列共计 N×MN \times M 个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

输入格式

第一行包含三个整数 NN 和 MM 和 TT，TT 表示 cl 对多少个摊点感兴趣。

接下来 TT 行，每行两个整数 x,yx, y，表示 cl 对处在第 xx 行第 yy 列的摊点感兴趣。

输出格式

首先输出一个字符串。

如果能满足 Vani 的全部两个要求，输出 both；

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；

如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；

如果均不能满足，输出 impossible。

如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围

1≤N,M≤1000001 \le N,M \le 100000,
0≤T≤min(N∗M,100000)0 \le T \le min(N*M,100000),
1≤x≤N1 \le x \le N,
1≤y≤M1 \le y \le M

输入样例：

1
2
3
4
5
2 3 4
1 3
2 1
2 2
2 3

输出样例：

1
row 1

算法分析

经过分析, 我们可以发现, 交换左右两个相邻的摊点只会改变某两列中 cl 感兴趣的摊点数, 不会改变每行中 cl 感兴趣的摊点数。同理, 交换上下两个相邻的摊点只会改变某两行中 clc l 感兴趣的摊点数, 不会改变每列中 cl 感兴趣的摊点数。所以我们可以 把本题分成两个互相独立的部分计算:

  1. 通过最少次数的左右交换使每列中 cl 感兴趣的摊点数相同。
  2. 通过最少次数的上下交换使每行中 cl\mathrm{cl} 感兴趣的摊点数相同。

以第 1 个问题为例进行探讨。

我们可以统计出在初始情况下, 每列中 cl 感兴趣的摊点总数, 记为 C[1]∼[M]C[1] \sim[M] 。 若 cl 感兴趣的摊点总数 TT 不能被 MM 整除, 则不可能达到要求。若 TT 能被 MM 整除, 则我们的目标就是让每列中有 T/MT / M 个 cl\mathrm{cl} 感兴趣的摊点。

思考到这里, 读者可能已经想到了一个与此类似的经典问题 “均分纸牌”。 “均分纸牌” 问题是说, 有 MM 个人排成一行, 他们手中分别有 C[1]∼C[M]C[1] \sim C[M] 张纸牌, 在每一步操作中, 可以让某个人把自己手中的一张纸牌交给他旁边的一个人, 求至少需要多少步操作才能让每个人手中持有的纸牌数相等。显然, 当所有人手中持有的纸牌总数 TT 能被 MM 整除时, “均分纸牌” 问题有解, 在有解时, 我们可以先考虑第一个人:

  1. 若 C[1]>T/MC[1]>T / M, 则第一个人需要给第二个人 C[1]−T/MC[1]-T / M 张纸牌, 即把 C[2]C[2] 加上 C[1]−T/MC[1]-T / M 。
  2. 若 C[1]<T/MC[1]<T / M, 则第一个人需要从第二个人手中拿 T/M−C[1]T / M-C[1] 张纸牌, 即把 C[2]C[2] 减去 T/M−C[1]T / M-C[1] 。

我们按照同样的方法依次考虑第 2∼M2 \sim M 个人。即使在某个时刻有某个 C[i]C[i] 被减为负数也没有关系, 因为接下来 C[i]C[i] 就会从 C[i+1]C[i+1] 处拿牌, 在实际中可以认为 C[i]C[i] 从 C[i+1]C[i+1] 处拿牌发生在 C[i−1]C[i-1] 从 C[i]C[i] 处拿牌之前。按照这种方法, 经过计算, 达到目标所需要的最少步数其实就是:

∑i=1M∣i∗TM−G[i]∣, 其中 G 是 C 的前缀和, 即 G[i]=∑j=1iC[j]\sum_{i=1}^{M}\left|i * \frac{T}{M}-G[i]\right| \text{, 其中 G 是 C 的前缀和, 即 }G[i]=\sum_{j=1}^{i} C[j]

其含义是每个 “前缀” 最初共持有 G[i]G[i] 张纸牌, 最终会持有 i∗T/Mi * T / M 张纸牌, 多退少补, 会与后边的人发生 “二者之差的绝对值” 张纸牌的交换。

如果我们设 A[i]=C[i]−T/MA[i]=C[i]-T / M, 即开始就让每个人手中的纸牌数都减掉 T/MT / M, 并且最终让每个人手里都恰好有 0 张纸牌, 答案显然不变, 就是:

∑i=1M∣S[i]∣, 其中 S 是 A 的前缀和, 即 S[i]=∑j=1iA[j]\sum_{i=1}^{M}|S[i]| \text {, 其中 } S \text { 是 } A \text { 的前缀和, 即 } S[i]=\sum_{j=1}^{i} A[j]

从数学的角度, 以上两个公式也可以互相推导得到。

回到本题, 如果不考虑 “第 1 列与最后一列也是相邻的” 这一条件, 那么刚才提到的本题中的第 1 个问题与 “均分纸牌” 问题是等价的。若问题有解, 一定存在一种适当的顺序, 使得每一步传递纸牌的操作可以转化为交换一对左右相邻的摊点 (其中 cl\mathrm{cl} 恰好对这两个摊点之一感兴趣)。

若第 1 列与最后一列相邻, 则问题等价于一个 “环形均分纸牌”。仔细思考可以发现,一定存在一种最优解的方案, 环上某两个相邻的人之间没有发生纸牌交换操作。于是有一种朴素的做法是, 枚举这个没有发生交换的位置, 把环断开看成一行, 转化为般的 “均分纸牌”问题进行计算。

首先, 一般的 “均分纸牌” 问题就相当于在第 MM 个人与第 1 个人之间把环断开, 此时这 MM 个人写成一行, 其持有的纸牌数、前缀和分别是:

A[1]S[1]A[2]S[2]⋯⋯A[M]S[M]\begin{array}{cc} A[1] & S[1] \\ A[2] & S[2] \\ \cdots & \cdots \\ A[M] & S[M] \end{array}

如果在第 kk 个人之后把环断开写成一行, 这 MM 个人持有的纸牌数、前缀和分别是:

A[k+1]S[k+1]−S[k]A[k+2]S[k+2]−S[k]……A[M]S[M]−S[k]A[1]S[1]+S[M]−S[k]……A[k]S[k]+S[M]−S[k]\begin{array}{cc} A[k+1] & S[k+1]-S[k] \\ A[k+2] & S[k+2]-S[k] \\ \ldots & \ldots \\ A[M] & S[M]-S[k] \\ A[1] & S[1]+S[M]-S[k] \\ \ldots & \ldots \\ A[k] & S[k]+S[M]-S[k] \end{array}

注意: 此处 AA 是减去最终每个人手里纸牌数 T/MT / M 之后的数组, AA 数组均分之后每个人手里都有 0 张纸牌, 所以 S[M]=0S[M]=0 。也就是说, 从第 kk 个人把环断开写成一行, 前缀和数组的变化是每个位置都减掉 S[k]S[k] 。

根据我们上面推导的公式, 所需最少步数为:

∑i=1M∣S[i]−S[k]∣, 其中 S 是 A 的前缀和, 即 S[i]=∑j=1iA[j]\sum_{i=1}^{M}|S[i]-S[k]| \text {, 其中 } S \text { 是 } A \text { 的前缀和, 即 } S[i]=\sum_{j=1}^{i} A[j]

当 kk 取何值时上式最小? 这就是上一题 “货仓选址” ! 其中 S[i]S[i] 是数轴上 MM 家商店的位置, S[k]S[k] 是货仓的位置, ∣S[i]−S[k]∣|S[i]-S[k]| 就是二者之间的距离。根本不需要枚举 kk, 只需要把 SS 从小到大排序, 取中位数作为 S[k]S[k] 就是最优解 ! 至此, 本题得到完美解决, 时间复杂度为 O(Nlog⁡N+Mlog⁡M)O(N \log N+M \log M) 。

综上所述, 本题可类比为行、列方向上的两次 “环形均分纸牌” 问题。环形均分纸牌又类比为 “均分纸牌” 与 “货仓选址” 问题。其中的每一步都仅使用了基本算法和性质, 最后转化为了简单而经典的问题。读者应该时刻把各种模型之间的简化、扩展和联系作为算法学习与设计的脉络, 以点成线, 触类旁通, 才能产生数量到质量的飞跃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 100006;
int n, m, t, x[N], y[N], a[N], s[N];

int main() {
	cin >> n >> m >> t;
	for (int i = 1; i <= t; i++) scanf("%d %d", &x[i], &y[i]);
	bool row = !(t % n), column = !(t % m);
	if (row) {
		if (column) cout << "both ";
		else cout << "row ";
	} else {
		if (column) cout << "column ";
		else {
			cout << "impossible" << endl;
			return 0;
		}
	}
	ll ans = 0;
	if (row) {
		int num = t / n;
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= t; i++) a[x[i]]++;
		for (int i = 1; i <= n; i++) a[i] -= num;
		s[0] = 0;
		for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
		sort(s + 1, s + n + 1);
		for (int i = 1; i <= n / 2; i++) ans += s[n-i+1] - s[i];
	}
	if (column) {
		int num = t / m;
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= t; i++) a[y[i]]++;
		for (int i = 1; i <= m; i++) a[i] -= num;
		s[0] = 0;
		for (int i = 1; i <= m; i++) s[i] = s[i-1] + a[i];
		sort(s + 1, s + m + 1);
		for (int i = 1; i <= m / 2; i++) ans += s[m-i+1] - s[i];
	}
	cout << ans << endl;
	return 0;
}

Solution

106. 动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

输入格式

第一行输入一个整数 PP，代表后面数据集的个数，接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数 MM，代表数据集中包含数据的个数，MM 一定为奇数，数据之间用空格隔开。

数据集的剩余行由数据集的数据构成，每行包含 1010 个数据，最后一行数据量可能少于 1010 个，数据之间用空格隔开。

输出格式

对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。

数据集的剩余行由输出的中位数构成，每行包含 1010 个数据，最后一行数据量可能少于 1010 个，数据之间用空格隔开。

输出中不应该存在空行。

数据范围

1≤P≤10001 \le P \le 1000,
1≤M≤999991 \le M \le 99999,
所有 MM 相加之和不超过 5×1055 \times 10^5。

输入样例：

1
2
3
4
5
6
7
8
9
3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

输出样例：

1
2
3
4
5
6
7
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

算法分析

本题有两种做法, 使用 “对顶堆” 的在线做法 (读入的同时即时计算答案) 和使用 “链表+Hash” 的离线做法 (完成所有读入后进行计算然后再统一输出)。

为了动态维护中位数, 我们可以建立两个二叉堆: 一个小根堆、一个大根堆。在依次读入这个整数序列的过程中, 设当前序列长度为 MM, 我们始终保持:

  1. 序列中从小到大排名为 1∼M/21 \sim M / 2 的整数存储在大根堆中;
  2. 序列中从小到大排名为 M/2+1∼MM / 2+1 \sim M 的整数存储在小根堆中。

任何时候, 如果某一个堆中元素个数过多, 打破了这个性质, 就取出该堆的堆顶插入另一个堆。这样一来, 序列的中位数就是小根堆的堆顶。

每次新读入一个数值 XX 后, 若 XX 比中位数小, 则插入大根堆, 否则插入小根堆, 在插入之后检查并维护上述性质即可。这就是 “对顶堆” 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
priority_queue<int> q1, q2;

void Running_Median() {
	while (q1.size()) q1.pop();
	while (q2.size()) q2.pop();
	int num, n;
	cin >> num >> n;
	cout << num << " " << (n + 1) / 2 << endl;
	int a;
	cin >> a;
	cout << a << " ";
	q2.push(-a);
	int cnt = 1;
	for (int i = 2; i <= n; i++) {
		scanf("%d", &a);
		if (a < -q2.top()) q1.push(a);
		else q2.push(-a);
		int s = q1.size();
		if (s > i / 2) {
			q2.push(-q1.top());
			q1.pop();
		}
		if (s < i / 2) {
			q1.push(-q2.top());
			q2.pop();
		}
		if (i % 2) {
			cout<< -q2.top() << " ";
			if (++cnt % 10 == 0) cout << endl;
		}
	}
	cout << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) Running_Median();
	return 0;
}

Solution

第 kk 大数

给定 nn 个整数, 如何求出第 kk 大的数? 我们当然可以直接对这 nn 个整数进行快速排序, 然后输出从大到小排在第 kk 个的数, 时间复杂度为 O(nlog⁡n)O(n \log n) 。实际上利用类似于快速排序的思想, 只需要 O(n)O(n) 的时间即可求出第 kk 大数。

从大到小进行快速排序算法的思想是, 在每一层递归中, 随机选取一个数为基准, 把比它大的数交换到 “左半段”, 把其余的数和基准值自身一起作为 “右半段”, 然后继续递归对左右两边分别进行排序, 在平均情况下快速排序的复杂度为 O(nlog⁡n)O(n \log n) 。

实际上在每次选取基准值后, 我们可以统计出大于基准值的数的数量 cntc n t, 如果 k≤cntk \leq c n t, 我们就在左半段 (比基准值大的数中) 寻找第 kk 大数; 如果 k>cntk>c n t, 我们就在右半段 (小于或等于基准值的数中) 寻找第 k−cntk-c n t 大数。因此, 寻找第 kk 大数 时, 我们只需要进入左右两半二者之一继续递归, 在平均情况下, 复杂度为 n+n/2+n+n / 2+ n/4+⋯+1=O(n)n / 4+\cdots+1=O(n) 。

逆序对

对于一个序列 aa, 若 i<ji<j 且 a[i]>a[j]a[i]>a[j], 则称 a[i]a[i] 与 a[j]a[j] 构成逆序对。使用归并排序可以在 O(nlog⁡n)O(n \log n) 的时间里求出一个长度为 nn 的序列中逆序对的个数。归并排序每次把序列二分, 递归对左右两半排序, 然后合并两个有序序列。

递归对左右两半排序时, 可以把左右两半各自内部的逆序对数作为子问题计算, 因此我们只需要在合并时考虑 “左边一半里一个较大的数” 与 “右边一半里一个较小的 数" 构成逆序对的情形, 求出这种情形的个数。

合并两个有序序列 a[l∼mid]a[l \sim m i d] 与 a[mid+1∼r]a[m i d+1 \sim r] 可以采用两个指针 ii 与 jj 分别对二者进行扫描的方式, 不断比较两个指针所指向数值 a[i]a[i] 和 a[j]a[j] 的大小, 将小的那个加入到排序的结果数组中。若小的那个是 a[j]a[j], 则 a[i∼mid]a[i \sim m i d] 都比 a[j]a[j] 要大, 它 们都会与 a[j]a[j] 构成逆序对, 可以顺便统计到答案中。

1
2
3
4
5
6
7
8
9
10
// 归并排序求逆序对
void merge(int l, int mid, int r) {
	// 合并a[l~mid]与a[mid+1~r]
	// a是待排序数组, b是临时数组, cnt是逆序对个数
	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++)
		if (j > r || i <= mid && a[i] < a[j]) b[k] = a[i++];
		else b[k] = a[j++], cnt += mid - i + 1;
	for (int k = l; k <= r; k++) a[k] = b[k];
}

求逆序对的常用方法还有树状数组。

107. 超快速排序

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理 nn 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数 nn，代表该用例中输入序列的长度。

接下来 nn 行每行输入一个整数 aia_i,代表用例中输入序列的具体数据，第 ii 行的数据代表序列中第 ii 个数。

当输入用例中包含的输入序列长度为 00 时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数 opop，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围

0≤n<5000000 \le n < 500000,
一个测试点中，所有 nn 的和不超过 500000500000。
0≤ai≤9999999990 \le a_i \le 999999999

输入样例：

1
2
3
4
5
6
7
8
9
10
11
5
9
1
0
5
4
3
1
2
3
0

输出样例：

1
2
6
0

算法分析

只通过比较和交换相邻两个数值的排序方法, 实际上就是冒泡排序。在排序过程中每找到一对大小颠倒的相邻数值, 把它们交换, 就会使整个序列的逆序对个数减少 1 。最终排好序后逆序对个数显然为 0 , 所以对 aa 进行冒泡排序需要的最少交换次数就是序列 aa 中逆序对的个数。我们直接使用归并排序求出 aa 的逆序对数就是本题的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//Author:XuHt
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 500006;
int n, a[N], b[N];
ll ans;

void merge(int l, int mid, int r) {
	if (l == r) return;
	if (l + 1 == r) {
		if (a[l] > a[r]) {
			ans++;
			swap(a[l], a[r]);
		}
		return;
	}
	merge(l, (l + mid) >> 1, mid);
	merge(mid + 1, (mid + 1 + r) >> 1, r);
	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++)
		if (j > r || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
		else {
			b[k] = a[j++];
			ans += mid - i + 1;
		}
	for (int k = l; k <= r; k++) a[k] = b[k];
}

void Ultra_QuickSort() {
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	ans = 0;
	merge(1, (1 + n) >> 1, n);
	cout << ans << endl;
}

int main() {
	while (cin >> n && n) Ultra_QuickSort();
	return 0;
}

Solution

108. 奇数码问题

你一定玩过八数码游戏，它实际上是在一个 3×33 \times 3 的网格中进行的，11 个空格和 1∼81 \sim 8 这 88 个数字恰好不重不漏地分布在这 3×33 \times 3 的网格中。

例如：

1
2
3
5 2 8
1 3 _
4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

1
2
3
5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个 n×nn \times n 的网格中进行，其中 nn 为奇数，11 个空格和 1∼n2−11 \sim n^2-1 这 n2−1n^2-1 个数恰好不重不漏地分布在 n×nn \times n 的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个 n=3n=3 的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式

多组数据，对于每组数据：

第 11 行输入一个整数 nn，nn 为奇数。

接下来 nn 行每行 nn 个整数，表示第一个局面。

再接下来 nn 行每行 nn 个整数，表示第二个局面。

局面中每个整数都是 0∼n2−10 \sim n^2-1 之一，其中用 00 代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出格式

对于每组数据，若两个局面可达，输出 TAK，否则输出 NIE。

数据范围

1≤n<5001 \le n < 500

输入样例：

1
2
3
4
5
6
7
8
9
10
3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0

输出样例：

1
2
TAK
TAK

算法分析

奇数码游戏两个局面可达, 当且仅当两个局面下网格中的数依次写成 1 行 n∗n−1n * n-1 个元素的序列后 (不考虑空格), 逆序对个数的奇偶性相同。例如题目描述中的第一个局面写成 [5  2  8  1  3  4  6  7][5\;2\;8\;1\;3\;4\;6\;7] 。该结论的必要性很容易证明: 空格左右移动时, 写成的序列显然不变; 空格向上 (下) 移动时, 相当于某个数与它后 (前) 边的 n−1n-1 个数交换了位置, 因为 n−1n-1 是偶数, 所以逆序对数的变化也只能是偶数。该结论的充分性证明较为复杂, 我们将不在此大篇幅讨论这样一个数学问题。

上面的结论还可以扩展到 nn 为偶数的情况, 此时两个局面可达, 当且仅当两个局面对应网格写成序列后, “逆序对数之差” 和 “两个局面下空格所在的行数之差” 奇偶性相同。事实上, 在 n∗mn * m 网格上 (n,m≥2)(n, m \geq 2) 也服从上述两个结论之一 (根据列数奇偶性分情况讨论)。

总而言之, n∗mn * m 数码问题的有解性判定, 可以转化为归并排序求逆序对来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;
long long ans;
vector<int> a[2];
int c[250010];

void merge(int k, int l, int mid, int r)
{
	int x = l, y = mid + 1;
	for (int i = l; i <= r; i++)
	{
		if (y>r || x <= mid&&a[k][x]<a[k][y])
			c[i] = a[k][x++];
		else ans += mid - x + 1, c[i] = a[k][y++];
	}
	for (int i = l; i <= r; i++) a[k][i] = c[i];
}

void mergesort(int k, int l, int r)
{
	if (l == r) return;
	int mid = (l + r) / 2;
	mergesort(k, l, mid);
	mergesort(k, mid + 1, r);
	merge(k, l, mid, r);
}

long long calc(int k)
{
	ans = 0;
	mergesort(k, 0, n*n - 1);
	return ans;
}

int main()
{
	while (cin >> n)
	{
		a[0].clear();
		a[1].clear();
		for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)
		{
			int x; scanf("%d", &x); if (x) a[0].push_back(x);
		}
		for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)
		{
			int x; scanf("%d", &x); if (x) a[1].push_back(x);
		}
		puts(a[0].size()&&(calc(1) - calc(0) & 1) ? "NIE" : "TAK");
	}
}

Solution