GESP认证C++编程真题解析 | P14917 [GESP202512 五级] 数字移动

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

---

【题目来源】

洛谷：[P14917 GESP202512 五级] 数字移动 - 洛谷

【题目描述】

小 A 有一个包含N NN个正整数的序列A = { A 1 , A 2 , ⋯ , A N } A=\{A_1,A_2,\cdots,A_N\}A={A1​,A2​,⋯,AN​}，序列A AA恰好包含N 2 \frac{N}{2}2N​对不同的正整数。形式化地，对于任意1 ≤ i ≤ N 1 \le i \le N1≤i≤N，存在唯一一个j jj满足1 ≤ j ≤ N , i ≠ j , A i = A j 1\le j \le N, i\neq j, A_i=A_j1≤j≤N,i=j,Ai​=Aj​。

小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意i ( 1 ≤ i ≤ N ) i(1\le i\le N)i(1≤i≤N)，将当前序列的第i ii个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列A = { 1 , 2 , 1 , 3 , 2 , 3 } A=\{1,2,1,3,2,3\}A={1,2,1,3,2,3}，小 A 可以选择i = 2 i=2i=2，将A 2 = 2 A_2=2A2​=2移动到A 3 = 1 A_3=1A3​=1的后面，此时序列变为{ 1 , 1 , 2 , 3 , 2 , 3 } \{1,1,2,3,2,3\}{1,1,2,3,2,3}，耗费2 22点体力。小 A 也可以选择i = 3 i=3i=3，将A 3 = 1 A_3=1A3​=1移动到A 2 = 2 A_2=2A2​=2的前面，此时序列变为{ 1 , 1 , 2 , 3 , 2 , 3 } \{1,1,2,3,2,3\}{1,1,2,3,2,3}，花费1 11点体力。

小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的x xx，使得他能够在每次花费的体力均不超过x xx的情况下令每对相同的数字在序列中相邻。

【输入】

第一行一个正整数N NN，代表序列长度，保证N NN为偶数。

第二行包含N NN个正整数A 1 , A 2 , … , A N A_1,A_2,\ldots,A_NA1​,A2​,…,AN​，代表序列A AA。且对于任意1 ≤ i ≤ N 1\le i\le N1≤i≤N，存在唯一一个j jj满足1 ≤ j ≤ N , i ≠ j , A i = A j 1\le j\le N,i\neq j,A_i=A_j1≤j≤N,i=j,Ai​=Aj​。

数据保证小 A 至少需要执行一次操作。

【输出】

输出一行，代表满足要求的x xx的最小值。

【输入样例】

6 1 2 1 3 2 3

【输出样例】

2

【算法标签】

《洛谷 P14917 数字移动》 #二分# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,a[N],maxn;// n: 数组元素个数, a: 存储数组, maxn: 最大值（代码中未使用）// 检查函数：验证是否能在限制x下使数组满足配对条件boolcheck(intx){intt=0;// 临时变量，用于记录当前等待配对的数字// 遍历数组中的每个元素for(inti=1;i<=n;i++){// 如果当前元素小于等于x，可以忽略if(a[i]<=x)continue;// 处理大于x的元素if(!t)// 如果t为0，表示没有等待配对的数字t=a[i];// 将当前数字设为需要配对的数字elseif(a[i]!=t)// 如果当前数字与等待配对的数字不同return0;// 无法满足条件，返回falseelse// 如果当前数字与等待配对的数字相同t=0;// 配对成功，重置t为0}// 如果最后t为0，说明所有大于x的数字都成功配对return1;}intmain(){cin>>n;// 输入数组长度// 读取数组元素for(inti=1;i<=n;i++)cin>>a[i];intl=1,r=100000;// 二分查找的左右边界，r设为最大值100000// 二分查找最小的xwhile(l<r){intmid=(l+r)/2;// 取中间值if(check(mid))// 如果mid满足条件r=mid;// 尝试更小的x，右边界缩小到midelsel=mid+1;// 否则需要更大的x，左边界增加到mid+1}cout<<l<<endl;// 输出最小满足条件的xreturn0;}

【运行结果】

6 1 2 1 3 2 3 2