202512-数字移动(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

6
1 2 1 3 2 3

输出 #1

说明/提示

对于 $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。

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 过程中的临时数组。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年1月5日

202509-有趣的数字和(luogu-P14074)