【GESP】C++ 五级真题解析，[2025年12月，第十二次认证]第一题-数字移动 luogu-p14917
GESP C++ 2025年12月，五级真题第一题，考察二分答案算法思想，在历届真题中属于相对少见的，对考试来说有一定难度。题目难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−。
P14917 [GESP202512 五级] 数字移动
题目要求
题目描述
小 A 有一个包含 $N$ 个正整数的序列 $A={A_1,A_2,\cdots,A_N}$，序列 $A$ 恰好包含 $\frac{N}{2}$ 对不同的正整数。形式化地，对于任意 $1 \le i \le N$，存在唯一一个 $j$ 满足 $1\le j \le N, i\neq j, A_i=A_j$。
小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 $i(1\le i\le N)$，将当前序列的第 $i$ 个数字移动到任意位置，并花费对应数字的体力。
例如，假设序列 $A={1,2,1,3,2,3}$，小 A 可以选择 $i=2$，将 $A_2=2$ 移动到 $A_3=1$ 的后面，此时序列变为 ${1,1,2,3,2,3}$，耗费 $2$ 点体力。小 A 也可以选择 $i=3$，将 $A_3=1$ 移动到 $A_2=2$ 的前面，此时序列变为 ${1,1,2,3,2,3}$，花费 $1$ 点体力。
小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 $x$，使得他能够在每次花费的体力均不超过 $x$ 的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数 $N$，代表序列长度，保证 $N$ 为偶数。
第二行包含 $N$ 个正整数 $A_1,A_2,\ldots,A_N$，代表序列 $A$。且对于任意 $1\le i\le N$，存在唯一一个 $j$ 满足 $1\le j\le N,i\neq j,A_i=A_j$。
数据保证小 A 至少需要执行一次操作。
输出格式
输出一行，代表满足要求的 $x$ 的最小值。
输入输出样例 #1
输入 #1
1
2
6
1 2 1 3 2 3
输出 #1
1
2
说明/提示
对于 $40\%$ 的测试点，保证 $1\le N,A_i\le 100$。
对于所有测试点，保证 $1\le N,A_i\le 10^5$。
题目分析
本题的核心在于理解“移动代价”与“位置重排”之间的关系。
1. 核心思路：二分答案
题目要求找到一个最小的代价上限 $x$，使得我们只移动所有 代价值 $\le x$ 的数字，就能让所有相同的数字相邻。
- 单调性：如果花费上限 $x$ 可以满足条件，那么花费上限 $x+1$ 一定也能满足（因为可移动的数字更多了）。反之，如果 $x$ 不满足，那么 $x-1$ 也一定不满足。
- 算法选择：这种具有单调性的“最小化最大值”或“最小化代价”的问题，非常适合使用 二分答案（Binary Search on Answer）。
我们不需要直接构造出移动方案，只需要在一个范围内二分查找这个代价 $x$，然后写一个 check(x) 函数来验证是否可行。
2. 验证策略：贪心思想
对于给定的代价上限 $x$：
- 可移动元素：凡是数值 $\le x$ 的元素，都可以消耗 $\le x$ 的体力任意移动。在逻辑上，我们可以认为它们是“液态”的，可以被抽离并插入到任何位置。只要剩下的“骨架”合法，这些数字总能塞回去。
- 不可移动元素：凡是数值 $> x$ 的元素，因为移动它需要消耗 $> x$ 的体力，超过了上限，所以它们必须保持原有的相对位置不动。
判定逻辑：
我们将序列中所有 $\le x$ 的数全部“拿走”，只留下 $> x$ 的数（保持相对顺序不变）。 剩下的这个子序列（我们称为“骨架”），必须满足“相邻元素两两相等”的结构（即 A A B B C C 的形式）。
- 如果不满足，说明这些不可移动的大数卡住了位置，导致无法配对，该 $x$ 不可行。
- 如果满足，说明大数已经归位，我们可以把之前拿走的小数（$\le x$）成对地插回骨架的缝隙中，该 $x$ 可行。
例如：序列 5 8 5 8，如果 $x=4$，则 5和8都不能动，剩 5 8 5 8，显然不满足 5 5 8 8 或 8 8 5 5，失败。 例如：序列 1 5 1 5，如果 $x=3$，1可以动，5不能动。拿走 1 后剩 5 5，满足条件。我们可以把 1 1 插在 5 5 前面或后面。
3. 算法步骤
- 确定二分范围：下界 $L$ 为数组中的最小值，上界 $R$ 为数组中的最大值。
- 二分查找：
- 取中间值 $mid$。
- 调用
check(mid)验证。 - 如果可行，说明代价 $mid$ 足够（甚至可能偏大），尝试更小的代价，更新 $R = mid$。
- 如果不可行，说明代价太小，需要更大的代价，更新 $L = mid + 1$。
- 编写
check(x)：- 遍历原数组，将所有 $> x$ 的数按顺序存入新数组
fixed。 - 检查
fixed数组：第 0 和 1 个是否相等，第 2 和 3 个是否相等……以此类推。 - 如果所有对子都匹配，返回 true，否则返回 false。
- 遍历原数组，将所有 $> x$ 的数按顺序存入新数组
4. 复杂度分析
- 时间复杂度：二分查找进行 $O(\log (\max A_i))$ 次，每次
check需要遍历数组 $O(N)$。总时间复杂度为 $O(N \log (\max A_i))$。在本题 $N=10^5$ 的数据规模下，计算量约为 $1.7 \times 10^6$，完全可以在 1 秒内通过。 - 空间复杂度：需要 $O(N)$ 的额外空间来存储
check过程中的临时数组。
示例代码
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
57
58
59
60
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
int a[100005];
int N;
// 检查函数：判断当保留大于 x 的元素时，是否满足“相邻元素两两相等”的条件（比如 2
// 2 5 5）
bool check(int x) {
// 定义一个向量 fixed，用于存储所有大于阈值 x 的元素
std::vector<int> fixed;
for (int i = 1; i <= N; i++) {
// 遍历原数组，筛选出大于 x 的数
if (a[i] > x) {
fixed.push_back(a[i]);
}
}
// 遍历筛选后的数组，每次步进 2，检查相邻两个元素是否相等
// 根据题目数据，fixed.size() 一定是偶数，所以不会越界
for (int i = 0; i < fixed.size(); i += 2) {
if (fixed[i] != fixed[i + 1]) {
return false; // 如果这一对不相等，说明不能完美配对，返回 false
}
}
return true;
}
int main() {
std::cin >> N;
int max = INT_MIN;
int min = INT_MAX;
for (int i = 1; i <= N; i++) {
std::cin >> a[i];
max = std::max(max, a[i]);
min = std::min(min, a[i]);
}
// 二分查找
// 目标：寻找满足 check(x) == true 的最小 x
// 也就是找到一个最小的阈值，使得消除 <= 阈值的数后，剩下的数能组成对子。
int l = min;
int r = max;
while (l < r) {
int mid = l + (r - l) / 2; // 防止 (l+r) 溢出，且向下取整
if (check(mid)) {
// 如果 mid 满足条件，尝试更小的 x，看能不能更小
// 答案可能是 mid，也可能在左边
r = mid;
} else {
// 如果 mid 不满足，说明阈值太小了，消除的数不够多（或者消除的不对）
// 答案一定在 mid 右边，mid 本身肯定不行
l = mid + 1;
}
}
std::cout << l << '\n';
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
