![《P14917 [GESP202512 五级] 数字移动》](http://pic.xiahunao.cn/yaotu/《P14917 [GESP202512 五级] 数字移动》)
题目背景对应的选择、判断题试题 - GESP 202512 C 五级 - 洛谷有题题目描述小 A 有一个包含 N 个正整数的序列 A{A1,A2,⋯,AN}序列 A 恰好包含 2N 对不同的正整数。形式化地对于任意 1≤i≤N存在唯一一个 j 满足 1≤j≤N,ij,AiAj。小 A 希望每对相同的数字在序列中相邻为了实现这一目的小 A 每次操作会选择任意 i(1≤i≤N)将当前序列的第 i 个数字移动到任意位置并花费对应数字的体力。例如假设序列 A{1,2,1,3,2,3}小 A 可以选择 i2将 A22 移动到 A31 的后面此时序列变为 {1,1,2,3,2,3}耗费 2 点体力。小 A 也可以选择 i3将 A31 移动到 A22 的前面此时序列变为 {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,ij,AiAj。数据保证小 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 vectorint A) { int n A.size(); vectorint last_pos; unordered_mapint, int first_pos; unordered_mapint, int count; unordered_mapint, vectorint 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; vectorint 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; }
题目背景对应的选择、判断题试题 - GESP 202512 C 五级 - 洛谷有题题目描述小 A 有一个包含 N 个正整数的序列 A{A1,A2,⋯,AN}序列 A 恰好包含 2N 对不同的正整数。形式化地对于任意 1≤i≤N存在唯一一个 j 满足 1≤j≤N,ij,AiAj。小 A 希望每对相同的数字在序列中相邻为了实现这一目的小 A 每次操作会选择任意 i(1≤i≤N)将当前序列的第 i 个数字移动到任意位置并花费对应数字的体力。例如假设序列 A{1,2,1,3,2,3}小 A 可以选择 i2将 A22 移动到 A31 的后面此时序列变为 {1,1,2,3,2,3}耗费 2 点体力。小 A 也可以选择 i3将 A31 移动到 A22 的前面此时序列变为 {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,ij,AiAj。数据保证小 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 vectorint A) { int n A.size(); vectorint last_pos; unordered_mapint, int first_pos; unordered_mapint, int count; unordered_mapint, vectorint 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; vectorint 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; }
到文件描述符的深度解析)
