13021.数字移动

markdown
复制
1# 数字移动 题解
2
3## 题目分析
4
5我们有一个长度为 \(N\)（偶数）的正整数序列 \(A\)，其中每个数值恰好出现两次，即共有 \(\frac{N}{2}\) 对相同的数字。每次操作可以花费等于某个数字的体力将该数字移动到序列的任意位置。小 A 希望**每次操作的花费都不超过 \(x\)**，并最终让每一对相同的数字在序列中都相邻。目标是找到这个最小的 \(x\)。
6
7一旦确定了阈值 \(x\)，体力花费超过 \(x\) 的数字（即值大于 \(x\) 的数字）就**完全不能移动**，只有值小于等于 \(x\) 的数字可以自由移动。因此问题可以重新描述为：
8
9> 存在一个临界值 \(x\)，不可移动的数字（值 \(> x\)）在原序列中的相对顺序不能改变；可移动的数字（值 \(\le x\)）可以被插入到任意位置。能否通过移动这些“轻”数字，使整个序列中每对相同的数字相邻？
10
11## 解题思路
12
13### 判定条件
14对于固定的 \(x\)，我们能否达成目标？
15
161. 所有 \(> x\) 的数字无法移动，它们在最终序列中的相对顺序与在原序列中（去掉 \(\le x\) 的数字后）完全相同。
172. 题目要求每对相同的数字相邻，那么对于任意一对值 \(>x\) 的相同数字，它们必须在最终序列中紧挨着。由于它们之间不能有不可移动的其他数字，因此**在原序列中删去所有 \(\le x\) 的数字后**，剩下的序列必须满足：每一对相邻的元素相等，即序列呈现出 `... v, v, w, w, ...` 的形式。
18
19也就是说，如果我们只保留 \(>x\) 的数字，并按原顺序排列，它们必须两两成对，且每一对中的两个元素相同。
20
213. 至于所有 \(\le x\) 的数字，它们可以随意移动，因此只要上述条件满足，我们总能通过插入这些“轻”数字来补全整个序列，使得所有相同的数字都相邻。
22
23因此，对于给定的 \(x\)，“可行”的判定条件简化为：
24
25> 将原序列中所有值大于 \(x\) 的元素按原顺序提取出来，检查这个新序列中是否每两个连续的元素都相等。
26
27### 二分答案
28我们要找最小的满足条件的 \(x\)。由于当 \(x\) 变大时，不可移动的元素变少，条件只会更容易满足（单调性）。因此可以对 \(x\) 进行二分查找：
29
30- 左边界 `L = 1`（正整数，最小可能花费）。
31- 右边界 `R = 10^5`（最大可能的 \(A_i\)，保险起见可以取 \(10^6\)）。
32- 每次取 `mid = (L + R) / 2`，调用判定函数检查是否可行。
33- 可行则记录答案并尝试更小的 `x`（`R = mid - 1`），否则增大 `x`（`L = mid + 1`）。
34
35## 算法说明
36
371. 读入 \(N\) 和序列 \(A\)。
382. 二分答案，范围 \([1, \max(A_i)]\)（代码中右边界统一设为 \(10^6\) 足够覆盖所有数据）。
393. 对于每个 `mid`，执行可行性检查：
40   - 遍历原序列，将 `a[i] > mid` 的元素依次存入数组 `b`。
41   - 遍历 `b`，检查 `b[0] == b[1]`, `b[2] == b[3]`, … 是否全部成立。若有一处不等，则不可行。
424. 输出满足条件的最小 `x`。
43
44**为什么只需要检查大数字？**  
45因为小数字可以被自由安排，它们不会成为阻碍。唯一的阻碍是不可移动的大数字夹在了一对相同数字中间，而判定条件恰好捕捉了这种情况。
46
47**边界说明**  
48题目保证“小 A 至少需要执行一次操作”，因此答案至少是某个元素的值，不会出现 `x = 0` 的情况。二分左边界设为 `1` 是安全的。
49
50## 时间复杂度分析
51
52- 二分查找的区间长度为 \(O(\max A)\)，每次 `while` 循环减半，迭代次数为 \(O(\log \max A)\)，在本题中约 20 次。
53- 每次判定需要遍历整个序列一次，复杂度 \(O(N)\)。
54- 总时间复杂度为 \(O(N \log \max A)\)，在 \(N, A_i \le 10^5\) 时完全可以接受。
55
56## 参考代码
57
58下面给出与题目提供的 C++ 参考代码等价的实现，并添加了详细注释。
59
60```cpp
61#include <iostream>
62#include <algorithm>
63using namespace std;
64
65const int N = 100010;
66int a[N], b[N];          // a 存放原序列, b 存放 >mid 的元素
67
68int main() {
69    int n;
70    cin >> n;
71    for (int i = 0; i < n; ++i) {
72        cin >> a[i];
73    }
74
75    int left = 1, right = 1000000, ans = right;  // 右边界适当放大
76    while (left <= right) {
77        int mid = (left + right) / 2;
78
79        // 提取所有 >mid 的元素
80        int pos = 0;
81        for (int i = 0; i < n; ++i) {
82            if (a[i] > mid) {
83                b[pos++] = a[i];
84            }
85        }
86
87        // 检查 b 是否两两相等
88        bool possible = true;
89        for (int i = 0; i < pos; i += 2) {
90            if (b[i] != b[i + 1]) {
91                possible = false;
92                break;
93            }
94        }
95
96        if (possible) {      // 当前 x=mid 可行，尝试更小的
97            ans = mid;
98            right = mid - 1;
99        } else {             // 不可行，需要更大的 x
100            left = mid + 1;
101        }
102    }
103
104    cout << ans << endl;
105    return 0;
106}

代码要点解释

1. 数组 b 的作用
   它只存储那些在当前 mid 下不可移动的元素。pos 记录元素个数，pos 必定是偶数（因为原序列所有数都成对出现），所以检查时步长为 2 不会越界。

2. possible 的判断
   如果 b 中连续的两个元素不等，就说明有一对相同的“大数字”被其它的大数字隔开了，无法通过移动小数字来使它们相邻，因此该 mid 不可行。

3. 二分边界
   right 可以设为序列中的最大值，但直接设一个较大的常数（如 (10^6)）也能正确运行，且对时间复杂度影响很小。

总结

本题通过分析“不可移动元素”的约束条件，将复杂的移动问题转化为对原序列的一个简单判定。然后利用判定条件的单调性，使用二分答案高效求解。这种“二分答案 + 贪心/构造判定”的技巧在 OI 中非常常见，希望同学们能熟练掌握。