一、题目描述
C++算法
GESP C++ 五级真题解析：数字移动
本文解析 GESP C++ 五级真题“数字移动”问题。题目要求将成对出现的数字移动到相邻位置，移动代价为数字本身大小。目标是找到最小的最大单次移动代价 X，使得所有大于 X 的数字在原序列中已自然成对。解决方案采用二分答案法：二分猜测 X，验证剩余不可移动的大数字是否按原顺序两两相同。若可行则尝试更小值，否则增大。该方法利用可行性单调性高效求解，避免了贪心策略的局部最优陷阱。
本文解析 GESP C++ 五级真题“数字移动”问题。题目要求将成对出现的数字移动到相邻位置，移动代价为数字本身大小。目标是找到最小的最大单次移动代价 X，使得所有大于 X 的数字在原序列中已自然成对。解决方案采用二分答案法：二分猜测 X，验证剩余不可移动的大数字是否按原顺序两两相同。若可行则尝试更小值，否则增大。该方法利用可行性单调性高效求解，避免了贪心策略的局部最优陷阱。
有一排数字在排队，每个数字都会出现两次。例如：1 2 1 3 2 3。
现在要求每一对相同的数字必须紧紧挨在一起。
操作规则如下：
例如：
1 → 花 1 点体力100 → 花 100 点体力不是问最少总共花多少体力，也不是问最少移动几次。
而是问：有没有一种办法，让每一次移动消耗的体力都 ≤ X，且这个 X 尽可能小。
换句话说，找一个最小的 X，只要禁止移动大于 X 的数字，剩下的数字还能不能自己乖乖地配对成功。
我们假设规定体力超过 X 的数字不能动，剩下的能不能排好？这件事只有两种结果：能做到或做不到。
如果 X = 10 能做到，那 X = 11、12、13……一定也能做到。 答案是单调的，可以用二分查找。
原序列：1 2 1 3 2 3
假设 X = 1：
2, 2, 3, 32 3 2 3 (注意：原序列中 1 被移除了，剩下的是 2, 1, 3, 2, 3 -> 过滤掉 <=1 的 1，剩下 2, 3, 2, 3)1 2 1 3 2 3，去掉 <=1 的数字（即 1），剩下 2 3 2 3。假设 X = 2：
3, 3 (大于 2 的)1 2 1 3 2 3，去掉 <=2 的数字（1, 2, 1, 2），剩下 3 3。所以最小 X = 2。
本题不是贪心问题。局部最优选择（先动小的）不能保证全局最优，存在反例。可行性判定具有单调性，所以适合用二分 + 判定。
| 特征 | 是否满足 |
|---|---|
| 答案有大小顺序 | ✅ |
| X 越大越容易成功 | ✅ |
| 可行性是单调的 | ✅ |
| 目标是最小可行 X | ✅ |
👉 标准'二分答案'模型。
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int pos;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
int left = 1, right = 1e6, ans = 1e6;
while(left <= right){
int mid = (left + right) / 2;
bool possible = true;
pos = 0;
for(int i = 0; i < n; i++){
if(a[i] > mid){
b[pos++] = a[i];
}
}
for(int i = 0; i < pos; i += 2){
if(b[i] != b[i+1]){
possible = false;
break;
}
}
if(possible){
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}
int left = 1, right = 1e6, ans = 1e6;
含义：X 最小可能是 1，最大可能是 1000000，ans 用来记住最终答案。
while(left <= right){ int mid = (left + right) / 2; }
含义：我们来试试，如果最大体力是 mid，行不行？
pos = 0;
for(int i = 0; i < n; i++){
if(a[i] > mid){
b[pos++] = a[i];
}
}
像一个筛子：数字 ≤ mid：可以动，先不管；数字 > mid：不能动，存进 b。
for(int i = 0; i < pos; i += 2){
if(b[i] != b[i+1]){
possible = false;
break;
}
}
规则：每两个必须一样，否则失败。
if(possible){
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
✅ 可以 → 尝试更小的 X；❌ 不行 → X 太小了，调大。
我们用二分查找猜一个最大体力 X，每次检查：所有'不能动的数字'能不能自己排成一对一对，最后找到最小的那个 X。
这道题不是让我们真的去移动数字，而是用聪明的办法判断——哪些数字'非动不可'，如果这些'大块头'自己都能排好队，那小数字怎么动都没问题！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
暂无推荐文章，稍后可再来查看。
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online