CCF-GESP计算机学会等级考试2025年12月五级C++T1 数字移动-编程实验室

P14917 [GESP202512 五级] 数字移动

题目描述

小 A 有一个包含NNN个正整数的序列A={A1,A2,⋯ ,AN}A=\{A_1,A_2,\cdots,A_N\}A={A1,A2,⋯,AN}，序列AAA恰好包含N2\frac{N}{2}2N对不同的正整数。形式化地，对于任意1≤i≤N1 \le i \le N1≤i≤N，存在唯一一个jjj满足1≤j≤N,i≠j,Ai=Aj1\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)，将当前序列的第iii个数字移动到任意位置，并花费对应数字的体力。

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

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

输入格式

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

第二行包含NNN个正整数A1,A2,…,ANA_1,A_2,\ldots,A_NA1,A2,…,AN，代表序列AAA。且对于任意1≤i≤N1\le i\le N1≤i≤N，存在唯一一个jjj满足1≤j≤N,i≠j,Ai=Aj1\le j\le N,i\neq j,A_i=A_j1≤j≤N,i=j,Ai=Aj。

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

输出格式

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

输入输出样例 #1

输入 #1

6 1 2 1 3 2 3

输出 #1

说明/提示

对于40%40\%40%的测试点，保证1≤N,Ai≤1001\le N,A_i\le 1001≤N,Ai≤100。

对于所有测试点，保证1≤N,Ai≤1051\le N,A_i\le 10^51≤N,Ai≤105。

题解：P14917 数字移动

一、题目核心分析

1. 题目本质

给定一个长度为偶数NNN的序列，序列中恰好包含N2\frac{N}{2}2N对不同的正整数（每个数字恰好出现两次）。我们需要找到最小的xxx，使得每次操作花费（移动数字的大小）均不超过xxx时，能让每对相同数字相邻。每次操作可将任意位置的数字移动到任意位置，花费为该数字的大小。

2. 解题核心思路

本题采用二分查找结合合法性校验的策略：

二分查找的范围：左边界left=0left=0left=0，右边界rightrightright为序列中的最大数字（因为最坏情况下需要移动最大的数字）。
合法性校验：对于给定的候选值xxx，判断是否能在每次操作花费不超过xxx的前提下，实现所有相同数字相邻。

// 引入万能头文件，包含C++所有常用标准库（如iostream、algorithm等），无需单独引入#include<bits/stdc++.h>// 使用std命名空间，避免每次调用库函数都写std::（如std::cin → cin）usingnamespacestd;constintMAXN=1e5+5;// 定义数组最大长度，1e5对应题目中N≤10^5的限制，+5防止越界intn;// 序列长度（全局变量，方便check函数直接访问）inta[MAXN];// 存储输入的序列/** * @brief 合法性校验函数：判断候选值x是否满足要求（每次操作花费≤x时能让所有相同数字相邻） * @param x 候选的最大允许花费 * @return bool true表示x合法，false表示不合法 */boolcheck(intx){intcnt=0;// 统计序列中>x的数字个数（这些数字无法移动，只能留在原位置）intpre=0;// 记录第奇数个>x的数字，用于匹配第偶数个>x的数字// 遍历整个序列，检查无法移动的数字是否能天然两两配对for(inti=1;i<=n;i++){// 若当前数字>x，说明移动它的花费超过x，无法移动，必须留在原位置if(a[i]>x){cnt++;// 无法移动的数字计数+1// 奇数个无法移动的数字：记录下来，等待后续配对if(cnt%2==1){pre=a[i];}// 偶数个无法移动的数字：必须和前一个（pre）相同，否则无法配对相邻else{if(a[i]!=pre){returnfalse;// 配对失败，x不合法}}}}// 所有无法移动的数字都成功两两配对，x合法returntrue;}intmain(){// 步骤1：输入处理 + 初始化二分查找边界cin>>n;// 读取序列长度nintleft=0;// 二分左边界：最小可能的花费（初始为0）intright=0;// 二分右边界：最大可能的花费（初始为0，后续更新为序列最大值）for(inti=1;i<=n;i++){cin>>a[i];// 读取序列的第i个元素right=max(right,a[i]);// 更新右边界为序列中的最大值（最坏情况需要移动最大数字）}// 步骤2：二分查找最小合法x（二分模板：寻找最小满足条件的值）// 循环条件：right > left + 1 → 确保最终收敛到最小合法值while(right>left+1){intmid=(left+right)/2;// 计算中间值（候选x）if(check(mid)){// 若mid合法（能通过校验）right=mid;// 尝试找更小的合法值，将右边界收缩到mid}else{// 若mid不合法left=mid;// 需要增大候选值，将左边界扩展到mid}}// 步骤3：输出结果（循环结束后，right即为最小合法x）// 原因：二分过程中right始终保持为合法值，left始终为不合法值，最终收敛到最小合法值cout<<right<<endl;return0;// 程序正常结束}

二、代码逻辑核心解读

1. 合法性校验函数核心逻辑

这是本题的核心函数，用于判断候选值xxx是否合法：

变量定义：
- cntcntcnt：统计序列中大于xxx的数字的个数（这些数字无法被移动，因为移动它们的花费会超过xxx，只能保留在原位置）。
- preprepre：记录第奇数个大于xxx的数字，用于匹配第偶数个大于xxx的数字。
遍历序列的核心逻辑：
1. 当遇到大于xxx的数字时（该数字无法移动），计数器cntcntcnt加 1。
2. 若cntcntcnt是奇数（当前是第1、3、5…个大于xxx的数字），将该数字存入preprepre，等待后续匹配。
3. 若cntcntcnt是偶数（当前是第2、4、6…个大于xxx的数字），必须与前一个（preprepre存储的）大于xxx的数字相同：
  - 若不相同，说明这两个无法移动的数字无法配对相邻，xxx不合法。
  - 若相同，说明这对数字可以自然配对，继续遍历。
遍历结束后，所有大于xxx的数字都成功两两配对，说明xxx合法。

关键逻辑解读：大于xxx的数字无法移动，因此它们必须在原序列中天然地两两出现（奇偶位置对应配对），否则无法实现相邻；而小于等于xxx的数字可以自由移动（花费不超过xxx），总能调整位置实现两两相邻。

2. 主函数核心逻辑

输入处理：读取序列长度nnn和序列数组，初始化二分查找的左右边界（左边界left=0left=0left=0，右边界rightrightright为序列中的最大数字）。
二分查找循环：
- 循环条件right>left+1：采用闭区间二分的优化写法，确保最终收敛到最小的合法xxx。
- 计算中间值mid=(left+right)/2mid=(left+right)/2mid=(left+right)/2（候选xxx）。
- 若候选值合法：说明midmidmid是合法值，尝试寻找更小的合法值，将右边界rightrightright更新为midmidmid。
- 若候选值不合法：说明midmidmid不合法，需要增大候选值，将左边界leftleftleft更新为midmidmid。
结果输出：循环结束后，rightrightright即为最小的合法值，输出rightrightright（核心原因：二分查找过程中，rightrightright始终保持为合法值，leftleftleft始终保持为不合法值，最终收敛时rightrightright是最小合法xxx）。

三、时间复杂度分析

二分查找次数：最多log⁡2(max(A))\log_2(max(A))log2(max(A))，由于Ai≤105A_i\le10^5Ai≤105，log⁡2(105)≈17\log_2(10^5)\approx17log2(105)≈17次。
每次合法性校验函数时间复杂度：O(n)O(n)O(n)，遍历一次序列。
总时间复杂度：O(nlog⁡max(A))O(n\log max(A))O(nlogmax(A))，满足n≤105n\le10^5n≤105的数据范围要求，运行高效。