当前位置：网硕互联帮助中心 > 服务器百科 > 正文

从一道GESP五级真题出发：聊聊二分答案与贪心判定的优雅组合

2026-09-06 分类：服务器百科阅读(26) 评论(0)

题源：洛谷 P14917 [GESP202512 五级] 数字移动题目链接

1. 背景

在算法竞赛中，"最小化最大值"类问题有着极其统一的解题框架——二分答案。这类问题的典型特征是：我们要求一个阈值

x

x

$x$ ，使得所有代价不超过

x

x

$x$ 的操作能够完成任务，且

x

x

$x$ 越小越好。如果直接求解最优

x

x

$x$ 很困难，但判断"给定

x

x

$x$ 是否可行"却相对容易，那么二分答案就是天然的选择。

本题正是这一思想的完美体现。序列中每个数字恰好出现两次，每次可以移动一个数字到任意位置，花费等于数字本身。我们需要找到一个最小的

x

x

$x$ ，使得只移动数值不超过

x

x

$x$ 的数字（即每次花费不超过

x

x

$x$ ），就能让所有相同数字在序列中相邻。

初看之下，这似乎是一个需要复杂贪心或动态规划的问题。但一旦你把"移动花费

≤

x

\\le x

$\leq x$ "理解为"数值

>

x

> x

$> x$ 的数字不能移动，必须待在原地"，问题就变得异常清晰：不可移动的数字必须在原始序列中（忽略可移动数字后）已经成对相邻。

本题在 GESP 五级中定位为"普及"难度，核心考察的是：

如何将"移动限制"转化为"固定元素"的条件；

如何设计高效的贪心判定函数；

如何利用二分答案处理"最小化最大值"类问题。

本文将从"正向思考移动"的直觉出发，逐步引导到"反向思考固定元素"的巧妙转化，带你掌握二分答案 + 贪心判定这一经典组合。

2. 核心思想章节

2.1 直觉先行：限制移动 vs 固定不可动

想象你有一排卡片，每张卡片上写着一个数字，每个数字恰好出现两次。你的目标是把相同的两张卡片挨在一起。每次操作可以拿起一张卡片插到任意位置，但代价是卡片上的数字——数字越大，搬动它越贵。

现在老板给你一个预算

x

x

$x$ ，只允许你搬动数字

≤

x

\\le x

$\leq x$ 的卡片。你想知道：给定这个预算，能不能完成任务？

换个角度想：数字

>

x

> x

$> x$ 的卡片不能搬动，所以它们的位置是"焊死"的。如果两张相同的卡片都是

>

x

> x

$> x$ ，那它们在最终序列中必须已经在相邻位置——因为它们的相对位置永远无法改变。即使中间隔着几张

≤

x

\\le x

$\leq x$ 的小卡片，那些小卡片可以被搬走，所以"相邻"的意思是：把可搬走的小卡片全部忽略后，这两张大卡片是挨着的。

于是问题变成了：把所有

≤

x

\\le x

$\leq x$ 的元素从序列中"删除"（因为它们可以被搬走），剩下的

>

x

> x

$> x$ 的元素组成的子序列，是否由若干对相邻的相同数字构成？

2.2 配对检查的贪心本质

现在我们已经把原始序列中所有

≤

x

\\le x

$\leq x$ 的元素"擦掉"了，剩下一个由

>

x

> x

$> x$ 元素组成的序列。怎么检查这个序列是否"成对相邻"呢？

从左到右扫描，用一个变量 last 记录当前"正在等待配对"的数字：

如果 last == 0，说明还没有等待配对的数字，当前数字就是新的配对起点，记下来；
如果 last 不为 0 且当前数字等于 last，配对成功，清空 last；
如果 last 不为 0 且当前数字不等于 last，说明出现了"交错"的情况（比如

为什么这样是正确且充分的？因为最终序列要满足"相同数字相邻"，等价于把每对相同数字看成一个"块"，块与块之间不能交叉。从左到右扫描时，一旦遇到一个未配对的数字，下一个出现的相同数字必须是紧挨着的，否则中间夹着其他数字，就不可能通过只移动小数字来修复（因为大数字不能动）。

2.3 单调性：为什么可以二分？

随着

x

x

$x$ 增大，允许移动的数字范围变大了，意味着：

更多的小数字可以被搬走，干扰项减少；
更多的大数字"降级"为可移动，原本可能造成错位的障碍被移除。

换句话说，

x

x

$x$ 越大，可行性越容易满足。这种单调性正是二分答案的基石：

如果
如果

于是我们可以二分最小的可行

x

x

$x$ ，从

1

1

$1$ 到

100000

100000

$100000$ （或数组最大值），每次

O

(

N

)

O(N)

$O (N)$ 判定，总复杂度

O

(

N

log

⁡

M

)

O(N \\log M)

$O (N lo g M)$ 。

2.4 为什么不能把

有人可能会想：既然

>

x

>x

$> x$ 的元素不能移动，那我能不能把它们的位置记录一下，然后看看每种数字的两个出现位置之间，是否所有其他元素都

≤

x

\\le x

$\leq x$ （即可以被移走）？

这个思路也是对的！实际上它和我们"删除

≤

x

\\le x

$\leq x$ 元素再配对"的方法等价。但后者更简洁：不需要记录位置，不需要计算区间，只需要一次扫描即可完成判定。这种"擦除小元素"的视角，让问题从"位置关系"变成了"序列结构"，大大简化了代码。

小结：本题的核心转化是"移动限制

→

\\to

$\to$ 固定元素

→

\\to

$\to$ 配对检查"。二分答案处理最小阈值，贪心判定处理可行性。这种"二分 + 贪心"的组合在竞赛中极其常见，是一个必须熟练掌握的套路。

3. 算法模板章节

3.1 算法到底在干什么？—— 直觉解释

你有一堆待整理的卡片。老板说："你只能搬动数字不超过

x

x

$x$ 的卡片，大卡片不许动。"你想知道能不能完成任务。

判断方法很简单：把所有小卡片（

≤

x

\\le x

$\leq x$ ）从队列里"抽走"（因为它们可以随便搬，不影响大卡片的相对顺序），然后看剩下的大卡片组成的队列，是不是"成双成对紧挨着"。

比如原始队列是 1 2 1 3 2 3，假设

x

=

1

x=1

$x = 1$ ：

小卡片（ $\\le 1 ≤1）有：第1个 1、第3个 1。抽走后剩下 2 3 2 3。$
检查 2 3 2 3：从左到右，2 等待配对，下一个是 3 不匹配 → 失败。所以

假设

x

=

2

x=2

$x = 2$ ：

小卡片（ $\\le 2 ≤2）有：1,2,1,2。抽走后剩下 3 3。$
检查 3 3：配对成功 → 可行。所以最小

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

check(x):
last = 0
for each val in A:
if val <= x:
continue // 可移动，忽略
if last == 0:
last = val // 开始等待配对
else if val == last:
last = 0 // 配对成功
else:
return false // 配对失败
return last == 0

二分查找最小的 x:
l = 1, r = max(A) 或 100000
while l < r:
mid = (l + r) / 2
if check(mid):
r = mid
else:
l = mid + 1
print(l)

完整 AC 代码（C++，带注释）：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n;
int a[N];

// 判定函数：给定限制 x，判断是否可行
// 核心思想：所有 > x 的元素不能移动，它们必须在忽略小元素后已经成对相邻
bool check(int x) {
int waiting = 0; // 0 表示没有等待配对的数字，否则存储当前等待配对的数字

for (int i = 1; i <= n; i++) {
// 可移动的小元素直接跳过（因为它们可以被移走，不影响大元素的相对顺序）
if (a[i] <= x) {
continue;
}

// 处理不可移动的大元素（> x）
if (waiting == 0) {
// 没有等待配对的数字，当前数字成为新的配对起点
waiting = a[i];
} else if (a[i] == waiting) {
// 找到了配对的数字，配对成功，重置等待状态
waiting = 0;
} else {
// 当前数字与等待配对的数字不同，说明大元素序列出现了交错
// 例如 [2, 3, 2, 3] 或 [2, 3, 3, 2] 都不行
return false;
}
}

// 遍历结束后，waiting 必须为 0（所有大元素都配对了）
return waiting == 0;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

// 二分答案：寻找最小的可行 x
// 左边界为 1（题目保证至少需要一次操作，所以答案至少为 1）
// 右边界设为 100000（根据题目数据范围，或取数组最大值）
int l = 1, r = 100000;

while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid; // mid 可行，尝试更小的值
} else {
l = mid + 1; // mid 不可行，需要更大的值
}
}

cout << l << endl;
return 0;
}

3.3 例题实现 —— 本题完整运行流程

以样例为例：

N = 6, A = [1, 2, 1, 3, 2, 3]

二分过程（

l

=

1

,

r

=

100000

l=1, r=100000

$l = 1, r = 100000$ ）：

mid = 50000：check 显然可行（所有元素都 <= 50000，可全部移走），r = 50000
mid = 25000：同样可行，r = 25000
… 二分不断缩小，直到 mid 来到

检查

x

=

1

x=1

$x = 1$ ：

遍历：1(跳过), 2(等待=2), 1(跳过), 3(等待=2 但当前=3 → 返回 false)
不可行，所以答案 > 1

检查

x

=

2

x=2

$x = 2$ ：

遍历：1(跳过), 2(跳过), 1(跳过), 3(等待=3), 2(跳过), 3(等待=3 且当前=3 → 配对成功)
遍历结束，waiting == 0，返回 true
可行，所以答案 <= 2

最终 l = 2，输出 2，与样例一致。✅

3.4 对比实现 —— 如果不用二分，直接贪心求答案？

有人可能会想：能不能不用二分，直接贪心求出最小

x

x

$x$ ？

比如，找到所有"导致配对失败的大元素对"，取其中的最大值作为答案？这种思路在本题中并不简单，因为

x

x

$x$ 变化时，哪些元素被"降级"为可移动是动态变化的，失败条件也在变化。直接求解需要复杂的扫描和更新逻辑。

而二分答案 + 判定函数的方式，把"求最优解"转化为"判定可行性"，每次判定的逻辑极其简单（

O

(

N

)

O(N)

$O (N)$ 扫描），总共只需要

log

⁡

M

\\log M

$lo g M$ 次判定，清晰且高效。这正是二分答案类问题的魅力所在。

3.5 变体清单

变体场景处理方法与本题的差异

每次移动花费等于数字的平方或位数	判定条件改为 a[i]^2 <= x 或 digit_count(a[i]) <= x	判定阈值不同
每个数字出现	配对逻辑改为：用计数器记录当前等待配对的数字出现次数，满	出现次数变化
需要输出具体移动方案	在 check 之外额外构造方案	本题只求阈值
目标不是"相邻"而是"有序排列"	判定逻辑改为检查剩余序列是否严格升序等	目标条件变化
允许移动	可引入二维状态或更复杂的 DP	约束更复杂
序列中数字出现次数不一定为 2	需要先统计每个数字的出现次数，然后配对逻辑按出现次数调整	出现次数不固定

3.6 什么时候不能用？

判定函数不具有单调性：如果
$10^9 109 甚至更大，二分仍然可行（ log ⁡ 10 9 ≈ 30 \\log 10^9 \\approx 30 log109≈30 次），但如果判定函数本身很慢（如 O ( N 2 ) O(N^2) O(N2)），则总复杂度可能过高。本题判定为 O ( N ) O(N) O(N)，非常高效。$
目标不是"最小值"而是"某种具体构造"：二分答案只求阈值，如果需要输出具体方案，还需要额外构造。
操作次数也有限制：如果除了花费限制外还有操作次数限制，判定函数需要额外记录操作数，可能变得复杂。

4. 底层逻辑章节

4.1 为什么"跳过 $\\le x ≤x 的元素"是安全的？$

关键在于：可移动元素可以被移走，也可以被移来，但它们不能改变不可移动元素的相对顺序。

当我们从原始序列中"删除"所有

≤

x

\\le x

$\leq x$ 的元素时，我们其实是在问：在最终目标序列中，所有

>

x

>x

$> x$ 的元素会以什么顺序出现？

由于

≤

x

\\le x

$\leq x$ 的元素可以被任意移动，它们可以在最终序列中填充任意位置，不会对

>

x

>x

$> x$ 元素之间的相对顺序造成任何限制。因此，

>

x

>x

$> x$ 元素在最终序列中的相对顺序，必须与它们在原始序列中的相对顺序完全相同（因为它们不能移动）。

而最终目标要求"相同数字相邻"，这意味着在最终序列中，

>

x

>x

$> x$ 元素的子序列必须由若干对相邻的相同数字组成。这与"在删除

≤

x

\\le x

$\leq x$ 元素后的子序列中，相同数字成对相邻"完全等价。

所以，跳过

≤

x

\\le x

$\leq x$ 元素再检查配对，不仅安全，而且是必要条件，也是充分条件。

4.2 为什么配对检查用"等待配对"就能覆盖所有情况？

考虑一个由

>

x

>x

$> x$ 元素组成的序列，每个数字出现两次。我们要检查它是否"成对相邻"（即形如

[

a

,

a

,

b

,

b

,

c

,

c

,

…

]

[a,a,b,b,c,c,\\dots]

$[a, a, b, b, c, c, \dots]$ 的形式）。

从左到右扫描，用 waiting 记录当前"正在等待其配对"的数字：

如果 waiting == 0，说明前面的部分已经全部配对完成，当前数字一定是一个新对的第一个元素。
如果 waiting != 0，说明我们正在等待某个数字的配对出现，当前数字必须恰好等于 waiting，否则就出现了交错。

这种"从左到右匹配括号"式的检查，本质上是判断序列是否属于正则语言

(

a

a

∣

b

b

∣

c

c

∣

.

.

.

)

∗

(aa|bb|cc|…)^*

$(aa ∣ bb ∣ cc ∣\dots)^{*}$ 。对于每个数字恰好出现两次的情况，这个检查是充分必要的。

4.3 与"括号匹配"的类比

如果把每个数字的出现看作一对括号——第一次出现是左括号，第二次出现是右括号——那么"相同数字相邻"就意味着括号对之间不能交叉（即不能出现

[

a

,

b

,

a

,

b

]

[a,b,a,b]

$[a, b, a, b]$ 这样的嵌套）。

而"删除

≤

x

\\le x

$\leq x$ 的元素"相当于移除一些括号对（或部分括号），剩下的大括号对必须已经是不交叉的。我们的 waiting 检查，本质上就是在检查剩余括号序列是否"合法嵌套"（但这里的"合法"是相邻匹配，不是括号匹配的栈式匹配，因为相邻匹配是更严格的条件）。

5. 决策表：不同思路的适用场景

场景方案时间复杂度空间复杂度优点缺点

求最小可行阈值	二分答案 + 贪心判定（本题解法）	$\\log M) O(NlogM)$		简洁高效，通用性强	需要判定函数有单调性
直接贪心求阈值	扫描所有数字，取"关键冲突"的最大值	可能		看似更快	逻辑复杂，容易出错
暴力枚举所有	从 1 到	$\\cdot M) O(N⋅M)$		简单直观	当
每个数字出现	二分判定中配对逻辑改为计数器	$\\log M) O(NlogM)$		扩展性好	判定逻辑略复杂
移动代价与位置有关	不能简单用阈值二分，需用 DP 或费用流	更高	更高	可处理复杂代价	实现难度大

6. 工程视角

"二分答案 + 贪心判定"这一范式在实际工程中有着广泛的应用：

任务调度中的资源分配：给定一系列任务，每个任务需要一定资源，求最小的资源上限使得所有任务可完成。典型应用包括云计算中的负载均衡、工厂生产线的产能分配等。

网络传输中的带宽限制：求最小带宽阈值，使得所有数据流能在不超过该带宽的情况下按时传输。判定函数通常用贪心或网络流实现。

物流配送中的车辆载重：求最小载重

代码审查中的"最大可容忍复杂度"：给定一系列代码模块的复杂度评分，求最小的复杂度阈值，使得超过该阈值的模块之间不形成依赖环（不可移动的高复杂度模块必须已经解耦）。

游戏平衡性中的数值调整：在卡牌游戏中，求最小的单卡强度上限，使得所有超过该上限的卡牌在原始卡组中已经"成对平衡"。

7. 小结

核心公式：

给定阈值

x

x

$x$ ，令序列

B

(

x

)

=

[

A

i

∣

A

i

>

x

]

B(x) = [A_i \\mid A_i > x]

$B (x) = [A_{i} ∣ A_{i} > x]$ （即删除所有

≤

x

\\le x

$\leq x$ 的元素）。

x

x

$x$ 可行当且仅当

B

(

x

)

B(x)

$B (x)$ 中的元素可以划分为若干对相邻的相同数字，即：

B

(

x

)

∈

(

a

1

a

1

a

2

a

2

⋯

a

k

a

k

)

其中

a

i

两两不同

B(x) \\in (a_1a_1a_2a_2\\cdots a_ka_k) \\quad \\text{其中 } a_i \\text{ 两两不同}

$B (x) \in (a_{1} a_{1} a_{2} a_{2} \dots a_{k} a_{k}) 其中 a_{i} 两两不同$

二分搜索最小的

x

x

$x$ 满足上述条件。

核心认知：

“最小化最大值"类问题，优先考虑二分答案。关键是把"求最优解"转化为"判定给定阈值是否可行”。
移动限制问题中，不可移动的元素是"锚点"，它们的相对顺序必须已经满足目标条件。可移动元素可以被忽略。
贪心判定函数要充分利用问题的结构——本题中"每个数字恰好出现两次"让配对检查变得极其简单。如果出现次数不同，判定逻辑需要相应调整。
二分答案的精髓在于单调性：阈值越大，限制越松，可行性越强。验证单调性是使用二分的前提。

本文完如果你觉得有帮助，欢迎点赞、收藏、转发，让更多算法爱好者看到~ 有任何疑问或建议，请在评论区留言交流。

赞(0)

未经允许不得转载：网硕互联帮助中心 » 从一道GESP五级真题出发：聊聊二分答案与贪心判定的优雅组合

标签：算法

相关推荐

评论抢沙发

评论前必须登录！

立即登录注册