每次可把某个数字移到任意位置、花费该数字的值;求最小的 x,使花费都不超过 x 时能让每对相同数字相邻。
序列 A 恰好包含 N/2 对不同的正整数(每个数都恰好出现两次)。每次操作可以选一个位置 i,把该位置的数字移动到任意位置,并花费该数字的值点体力。
求最小的 x,使得在每次花费都不超过 x 的前提下,能让每对相同的数字在序列中相邻。
例:A = 1 2 1 3 2 3 → 答案是 2。
二分答案相对顺序不变可行性检验成对相邻
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N(偶数);第二行 N 个数 |
| 输出 | 最小的 x |
| 数据范围 | 1 ≤ N, Aᵢ ≤ 10⁵ |
| 序列性质 | 每个数恰好出现两次 |
| 操作代价 | 移动一个值为 v 的数花费 v |
v v w w … 的形式(每个值的两次出现紧挨着)值有 1、2、3,各出现两次。我们分别检验 x = 1 和 x = 2。
可以移动的:值为 1 的数(出现 2 次)
不能移动的:值为 2、3 的数
按原顺序抽出不能动的数:
位置 2 是 2、位置 4 是 3、位置 5 是 2、位置 6 是 3
所以抽出序列是 2, 3, 2, 3
检查:值为 2 的两次出现在第 1、3 位 → 不相邻 ✗
❌ x = 1 不可行
可以移动的:值为 1、2 的数
不能移动的:只有值为 3 的数
按原顺序抽出:位置 4 的 3、位置 6 的 3
所以抽出序列是 3, 3
检查:相邻 ✅
✅ x = 2 可行
| x | 不能动的数 | 抽出的序列 | 每对相邻? | 可行 |
|---|---|---|---|---|
| 0 | 1,2,3(全部) | 1,2,1,3,2,3 | ❌ | 否 |
| 1 | 2,3 | 2,3,2,3 | ❌ | 否 |
| 2 | 3 | 3,3 | ✅ | 是 |
| 3 | (无) | (空) | ✅(空序列视为可行) | 是 |
最小的可行 x = 2 ✓
1 1 2 2 3 3 的形式。所以二分上界取最大值一定可行,保证二分会收敛。检验通过只说明"理论上可行",我们实际动手排一遍。
1 2 1 3 2 3
不能动的 3 在位置 4 和 6
3 的位置 4、6
位置 5 的 2 夹在两个 3 之间
把它移到开头(花费 2 ≤ x = 2 ✓)
得到 2 1 2 1 3 3
3 现在相邻了 ✓
剩下的 1、2、1、2 可以任意重排
搬成 1 1 2 2 的形式
最终 1 1 2 2 3 3
✅ 全部相邻
所有移动花费都不超过 2 ✓
可动的数之所以总能配对好,是因为每个值恰好出现两次——所以可动的数一定由"完整的对"组成,我们可以把它们成对地摆在一起。如果某个可动的值只出现一次,那就无法配对了,幸好题目保证了"每个数恰好两次"这个前提。
二分 x,每次 O(N) 抽出不能动的数检查相邻性
分析哪些数之间必然冲突,直接推出答案
| 方案 | 复杂度 | 实现难度 |
|---|---|---|
| 二分答案 | O(N log V) | 低 |
| 直接推导 | O(N) | 高(易漏情况) |
输入一个"每数恰好两次"的序列,程序会二分求出最小的 x。
点按钮开始 →
#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; }
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 | 二分 | 可行就试着更小,不可行就增大 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 2 | 题面样例 |
2 | 0 | 已经相邻,不需要操作 |
4 | 0 | 每对都已相邻 |
4 | 1 | x = 0 时抽出 1,2,1,2 不合;x = 1 时抽出 2,2 ✅ |
6 | 运行验证 | 含重复超过两次,超出题意 |
hi = mid - 1)。检验时需要临时数组存放抽出的数,O(N)。
✅ 约 170 万次操作,瞬间完成。关键洞察是"不能动的数相对顺序不变"。
// 二分答案求"最小可行值"的模板 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²",算法的框架变吗?(提示:框架不变——仍然是"二分上限 x",只是判断"某个数能否移动"时,条件变成 v² ≤ x 而不是 v ≤ x。这说明二分答案的框架对"代价函数"的具体形式不敏感。)