编程题
P14917 数字移动
【题目来源】
洛谷：[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\) 的最小值。
【输入样例】
6
1 2 1 3 2 3
【输出样例】
2
【算法标签】
《洛谷 P14917 数字移动》 #二分# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N], maxn; // n: 数组元素个数, a: 存储数组, maxn: 最大值（代码中未使用）// 检查函数：验证是否能在限制x下使数组满足配对条件
bool check(int x)
{int t = 0; // 临时变量，用于记录当前等待配对的数字// 遍历数组中的每个元素for (int i = 1; i <= n; i++){// 如果当前元素小于等于x，可以忽略if (a[i] <= x) continue;// 处理大于x的元素if (!t) // 如果t为0，表示没有等待配对的数字t = a[i]; // 将当前数字设为需要配对的数字else if (a[i] != t) // 如果当前数字与等待配对的数字不同return 0; // 无法满足条件，返回falseelse // 如果当前数字与等待配对的数字相同t = 0; // 配对成功，重置t为0}// 如果最后t为0，说明所有大于x的数字都成功配对return 1;
}int main()
{cin >> n; // 输入数组长度// 读取数组元素for (int i = 1; i <= n; i++)cin >> a[i];int l = 1, r = 100000; // 二分查找的左右边界，r设为最大值100000// 二分查找最小的xwhile (l < r){int mid = (l + r) / 2; // 取中间值if (check(mid)) // 如果mid满足条件r = mid; // 尝试更小的x，右边界缩小到midelse l = mid + 1; // 否则需要更大的x，左边界增加到mid+1}cout << l << endl; // 输出最小满足条件的xreturn 0;
}
【运行结果】
6
1 2 1 3 2 3
2
P14918 相等序列
【题目来源】
洛谷：[P14918 GESP202512 五级] 相等序列 - 洛谷
【题目描述】
小 A 有一个包含 \(N\) 个正整数的序列 \(A=\{A_1,A_2,\ldots,A_N\}\)。小 A 每次可以花费 \(1\) 个金币执行以下任意一种操作：
- 选择序列中一个正整数 \(A_i\)（\(1\le i\le N\)），将 \(A_i\) 变为 \(A_i\times P\)，\(P\) 为任意质数；
- 选择序列中一个正整数 \(A_i\)（\(1\le i\le N\)），将 \(A_i\) 变为 \(\frac{A_i}{P}\)，\(P\) 为任意质数，要求 \(A_i\) 是 \(P\) 的倍数。
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
【输入】
第一行一个正整数 \(N\)，含义如题面所示。
第二行包含 \(N\) 个正整数 \(A_1,A_2,\ldots,A_N\)，代表序列 \(A\)。
【输出】
输出一行，代表最少需要花费的金币数量。
【输入样例】
5
10 6 35 105 42
【输出样例】
8
【解题思路】
【算法标签】
《洛谷 P14918 相等序列》 #贪心# #数论# #素数判断,质数,筛法# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N][20], p[10005], cur, isprime[100005], ans; // n: 数字个数, a: 存储质因数统计, p: 质数数组, cur: 质数个数, isprime: 判断质数并存储索引, ans: 答案int main()
{cin >> n; // 输入数字个数// 埃拉托色尼筛法预处理质数for (int i = 2; i <= 100000; i++){if (!isprime[i]) // 如果i是质数{p[++cur] = i; // 将质数i存入数组pisprime[i] = cur; // 记录质数i在数组p中的索引for (int j = i + i; j <= 100000; j += i) // 标记i的所有倍数isprime[j] = 1; // 标记为非质数} }// 处理输入的n个数字for (int i = 1; i <= n; i++){int x;cin >> x; // 输入一个数字// 分解质因数for (int j = 1; p[j] * p[j] <= x; j++) // 只需检查到sqrt(x){if (x % p[j] == 0) // 如果p[j]是x的质因数{int cnt = 0; // 记录当前质因数的指数while (x % p[j] == 0) // 计算质因数p[j]的指数{cnt++;a[j][cnt]++; // 统计第j个质数的cnt次方在n个数字中出现的次数x /= p[j]; // 除掉这个质因数}}}if (x) // 如果x还有剩余的质因数（x本身是质数且大于sqrt(原x)）a[isprime[x]][1]++; // 统计这个质数的一次方}// 计算结果for (int i = 1; i <= cur; i++) // 遍历所有质数for (int j = 1; a[i][j]; j++) // 遍历第i个质数的所有指数{if (a[i][j] > n / 2) // 如果该质因子指数出现的次数超过一半ans += n - a[i][j]; // 添加需要改变的个数elseans += a[i][j]; // 添加该指数出现的次数}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
5
10 6 35 105 42
8