GESP 题解库 / 5 级题解 / [GESP202512 五级] 数字移动 · 第 4 / 23 题
GESP202512 五级 · P14917 · 中等

数字移动

每次可把某个数字移到任意位置、花费该数字的值;求最小的 x,使花费都不超过 x 时能让每对相同数字相邻。

📊
N, Aᵢ ≤ 10⁵
数据范围
🔢
int
数值类型
⚡
O(N log N)
时间复杂度
🎯
二分答案 + 相对顺序不变
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

序列 A 恰好包含 N/2 对不同的正整数(每个数都恰好出现两次)。每次操作可以选一个位置 i,把该位置的数字移动到任意位置,并花费该数字的值点体力。

求最小的 x,使得在每次花费都不超过 x 的前提下,能让每对相同的数字在序列中相邻。

例:A = 1 2 1 3 2 3 → 答案是 2。

💡
人话翻译:"每次花费不超过 x"意味着值大于 x 的数字完全不能动,只有值 ≤ x 的数字才能被移动。所以这题是"二分答案 x + 检验可行性"。而检验的关键在于:不能动的数字(值 > x)之间的相对顺序永远不变。

🔍 关键词提取

二分答案相对顺序不变可行性检验成对相邻

已知条件

项目说明
输入第一行 N(偶数);第二行 N 个数
输出最小的 x
数据范围1 ≤ N, Aᵢ ≤ 10⁵
序列性质每个数恰好出现两次
操作代价移动一个值为 v 的数花费 v

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 二分 x + 抽出不动的数检验
🎯 二分什么
二分答案 x
x 越大越容易(能动的数更多)
有单调性
在 [0, max(A)] 内二分
🧲 检验方法
把值 > x 的数按原序抽出
看它们是否形如 v v w w…
即每个值的两次出现相邻
是 → 可行
🧠 为什么对
不能动的数保持相对顺序
能动的数可搬到任意位置
所以只有"不动数之间是否夹着另一个不动数"要紧
能动的数总能配对好
⚠️ 易错点
以为检验条件与具体位置有关
二分上界取错
忘记 x 必须是某个出现过的值
没注意"至少需要一次操作"
03
样例手算推导
样例的检验过程

🧮 样例:A = 1 2 1 3 2 3,答案 2

值有 1、2、3,各出现两次。我们分别检验 x = 1 和 x = 2。

1
检验 x = 1

可以移动的:值为 1 的数(出现 2 次)

不能移动的:值为 2、3 的数

按原顺序抽出不能动的数:

位置 2 是 2、位置 4 是 3、位置 5 是 2、位置 6 是 3

所以抽出序列是 2, 3, 2, 3

检查:值为 2 的两次出现在第 1、3 位 → 不相邻 ✗

❌ x = 1 不可行

2
检验 x = 2

可以移动的:值为 1、2 的数

不能移动的:只有值为 3 的数

按原顺序抽出:位置 4 的 3、位置 6 的 3

所以抽出序列是 3, 3

检查:相邻 ✅

✅ x = 2 可行

📊 汇总

x不能动的数抽出的序列每对相邻?可行
01,2,3(全部)1,2,1,3,2,3❌否
12,32,3,2,3❌否
233,3✅是
3(无)(空)✅(空序列视为可行)是

最小的可行 x = 2 ✓

🔑
注意 x = 3 时"不能动的数"是空集,此时检验总是通过——因为所有数都能动,总能排成 1 1 2 2 3 3 的形式。所以二分上界取最大值一定可行,保证二分会收敛。

🧮 手工验证 x = 2 确实能做到

检验通过只说明"理论上可行",我们实际动手排一遍。

1
原始序列

1 2 1 3 2 3

不能动的 3 在位置 4 和 6

3 的位置 4、6

2
把夹在中间的数搬走

位置 5 的 2 夹在两个 3 之间

把它移到开头(花费 2 ≤ x = 2 ✓)

得到 2 1 2 1 3 3

3 现在相邻了 ✓

3
整理剩下可动的数

剩下的 1、2、1、2 可以任意重排

搬成 1 1 2 2 的形式

最终 1 1 2 2 3 3

✅ 全部相邻

所有移动花费都不超过 2 ✓

💡 一个理解要点

可动的数之所以总能配对好,是因为每个值恰好出现两次——所以可动的数一定由"完整的对"组成,我们可以把它们成对地摆在一起。如果某个可动的值只出现一次,那就无法配对了,幸好题目保证了"每个数恰好两次"这个前提。

04
解法对比
二分答案 vs 直接推答案

⚔️ 解法对比

🟢 二分答案 + 抽取检验(推荐) 推荐

二分 x,每次 O(N) 抽出不能动的数检查相邻性

  • 时间 O(N log V)
  • 约 17 轮 × N
  • 逻辑清晰
  • 代码 30 行
💡
可行性单调:x 越大,能动的数越多、不能动的数越少,检验就越容易通过。所以可行域是"从某个值往上全部可行",可以二分求最小可行值。

🟠 直接找"必须保留"的冲突

分析哪些数之间必然冲突,直接推出答案

  • 需要细致的分类讨论
  • 容易漏情况
  • 但可以做到 O(N) 一次扫描
  • 实现难度反而更高
⚠️
结论:本题的"二分 + 检验"框架虽然多一个 log 因子,但胜在思路清晰、不容易写错。而且 N ≤ 10⁵,log 因子完全可以接受。

📈 性能对比

方案复杂度实现难度
二分答案O(N log V)低
直接推导O(N)高(易漏情况)
05
算法流程图
二分 x,抽取不动数检查
开始读入 N 和序列 A;记录每个值出现的位置二分区间 lo = 0,hi = max(A)当 lo <= hi:取 mid = (lo + hi) / 2按原顺序抽出所有值 > mid 的数,得到序列 BB 中每个值的两次出现都相邻吗?是 ✓记录答案,hi = mid − 1否 ✗lo = mid + 1输出记录的最小可行 x结束二分区间还有效 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 最小移动花费上限

输入一个"每数恰好两次"的序列,程序会二分求出最小的 x。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int n;
int a[100005];

// 检验:当"花费上限为 x"时,能否让每对相邻
bool can(int x) {
    vector<int> b;
    for (int i = 0; i < n; i++)
        if (a[i] > x) b.push_back(a[i]);   // 抽出不能动的数(保持原顺序)

    // b 必须恰好是 v v w w ... 的形式
    if (b.size() % 2 != 0) return false;
    for (size_t k = 0; k + 1 < b.size(); k += 2)
        if (b[k] != b[k + 1]) return false;

    return true;
}

int main() {
    scanf("%d", &n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        mx = max(mx, a[i]);
    }

    // 二分最小的可行 x
    int lo = 0, hi = mx, ans = mx;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (can(mid)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么"抽出的序列必须是 v v w w …"?因为不能动的数之间相对顺序绝对不变,而它们最终必须两两相邻。如果抽出的序列是 2, 3, 2, 3,那么两个 2 之间永远夹着一个 3(3 也不能动),2 和 2 永远无法相邻。反之如果是 2, 2, 3, 3 就刚好成对 ✓。

📖 关键几行怎么看

代码作用为什么这样写
if (a[i] > x) b.push_back(a[i])抽取不动数按原顺序抽出,顺序信息很重要
if (b.size() % 2 != 0) return false长度检查成对出现,长度必须是偶数
if (b[k] != b[k+1]) return false相邻检查每两位必须相等
hi = mid - 1 / lo = mid + 1二分可行就试着更小,不可行就增大
⚠️
三个坑:① 把检验写成"看原序列里是否相邻"(应该看抽取后的序列);② 二分写反(可行时应往小的一侧收缩);③ 忘记"可动的数一定能配对好"这个前提来自"每数恰好两次"。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6
1 2 1 3 2 3
2题面样例
2
5 5
0已经相邻,不需要操作
4
2 2 1 1
0每对都已相邻
4
1 2 1 2
1x = 0 时抽出 1,2,1,2 不合;x = 1 时抽出 2,2 ✅
6
3 1 3 1 3 3
运行验证含重复超过两次,超出题意
✅
自查清单:① 抽出的是值 > x 的数吗?② 检查了 v v w w 形式吗?③ 二分方向对吗?

🚨 易错点清单

⚠️
检验用错对象:必须把不能动的数抽出来再检查相邻性,不能直接看原序列。
⚠️
二分方向反:可行时应尝试更小的 x(hi = mid - 1)。
⚠️
忽略"每数恰好两次":这是"可动的数一定能配好对"的保证。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log V)
空间复杂度
O(N)
N 最大
10⁵
V = max(A)
10⁵

时间怎么算的?

空间都用在哪?

检验时需要临时数组存放抽出的数,O(N)。

✅ 约 170 万次操作,瞬间完成。关键洞察是"不能动的数相对顺序不变"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 二分答案求"最小可行值"的模板
int lo = 0, hi = 上界, ans = 上界;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (can(mid)) { ans = mid; hi = mid - 1; }   // 可行 -> 试更小
    else lo = mid + 1;                            // 不可行 -> 增大
}

// "相对顺序不变"是很多题的突破口
// 例如:只允许交换相邻元素 -> 逆序对
//       只允许删除元素   -> 子序列问题
//       部分元素不可移动 -> 本题

// 判断"某序列是否形如 v v w w ..."
for (size_t k = 0; k + 1 < b.size(); k += 2)
    if (b[k] != b[k + 1]) return false;

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
二分答案单调性 + O(N) 检验最大化最小值、最小化最大值
相对顺序不变保留顺序的子序列删除/移动类问题的核心观察
可行性判定把约束化简为局部检查所有构造类问题
🌟
思考题:如果操作改成"移动一个数为 v 的数需要花费 v²",算法的框架变吗?(提示:框架不变——仍然是"二分上限 x",只是判断"某个数能否移动"时,条件变成 v² ≤ x 而不是 v ≤ x。这说明二分答案的框架对"代价函数"的具体形式不敏感。)