《P14917 [GESP202512 五级] 数字移动》

题目背景

对应的选择、判断题：试题 - GESP 202512 C++ 五级 - 洛谷有题

题目描述

小 A 有一个包含 N 个正整数的序列 A={A1​,A2​,⋯,AN​}，序列 A 恰好包含 2N​ 对不同的正整数。形式化地，对于任意 1≤i≤N，存在唯一一个 j 满足 1≤j≤N,i=j,Ai​=Aj​。

小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 i(1≤i≤N)，将当前序列的第 i 个数字移动到任意位置，并花费对应数字的体力。

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

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

输入格式

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

第二行包含 N 个正整数 A1​,A2​,…,AN​，代表序列 A。且对于任意 1≤i≤N，存在唯一一个 j 满足 1≤j≤N,i=j,Ai​=Aj​。

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

输出格式

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

输入输出样例

输入 #1复制

6 1 2 1 3 2 3

输出 #1复制

2

说明/提示

对于 40% 的测试点，保证 1≤N,Ai​≤100。

对于所有测试点，保证 1≤N,Ai​≤105。

代码实现：

#include <bits/stdc++.h> using namespace std; bool check(int x, const vector<int>& A) { int n = A.size(); vector<int> last_pos; unordered_map<int, int> first_pos; unordered_map<int, int> count; unordered_map<int, vector<int>> positions; for (int i = 0; i < n; i++) { positions[A[i]].push_back(i); } for (auto& p : positions) { int val = p.first; if (val <= x) continue; auto& pos = p.second; if (pos.size() != 2) continue; for (int i = pos[0] + 1; i < pos[1]; i++) { if (A[i] > x) { return false; } } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<int> A(N); int maxVal = 0; for (int i = 0; i < N; i++) { cin >> A[i]; maxVal = max(maxVal, A[i]); } int left = 1, right = maxVal, ans = maxVal; while (left <= right) { int mid = (left + right) / 2; if (check(mid, A)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } cout << ans << "\n"; return 0; }