202512-1 数字移动#

题目描述

小 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$ 的最小值。

样例输入 1

6
1 2 1 3 2 3

样例输出 1

2

提示

对于 $40\%$ 的测试点，保证 $1\le N,A_i\le 100$。

对于所有测试点，保证 $1\le N,A_i\le 10^5$。

代码解析

题目意思是移动数字让相同的数字相邻，每次移动某个数字，就会耗费对应数字的体力，也就是说我们要尽可能移动小的数字，题目求的是最小的 $x$。

二分答案解题，这道题满足二分答案的条件，我们可以二分 $mid$，判断是否能够在移动的数字不超过 $mid$ 的情况下令每对相同的数字在序列中相邻。那么 check() 函数中，我们需要遍历序列，找出所有大于 $mid$ 的数字，判断他们是否相邻，如果有不相邻的，就说明需要移动，就返回 false，如果所有大于 $mid$ 的数字都相邻，就返回 true。

1
#include <iostream>
2
using namespace std;
3
int a[100005], n, m;
4
bool check(int mid) {
5
    int lst = 0;
6
    for (int i = 1; i <= n; i++) {
7
        if (a[i] <= mid) continue;
8
        if (lst == a[i]) lst = 0;
9
        else if (a[i] > mid && lst > mid)
10
            return false;
11
        else lst = a[i];
12
    }
13
    return true;
14
}
15

16
int main() {
17

18
    cin >> n;
19
    for (int i = 1; i <= n; i++) {
20
        cin >> a[i];
21
        m = max(m, a[i]);
22
    }
23
    int mid, l = 1, r = m;
24
    while (l < r) {
25
        mid = (l + r) / 2;
26
        if (check(mid))
27
            r = mid;
28
        else
29
            l = mid + 1;
30
    }
31
    cout << r;
32

33
    return 0;
34
}

202512-2 相等序列#

题目描述

小 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$。

输出格式

输出一行，代表最少需要花费的金币数量。

样例输入 1

5
10 6 35 105 42

样例输出 1

8

提示

对于 $60\%$ 的测试点，保证 $1\le N,A_i\le 100$。

对于所有测试点，保证 $1\le N,A_i\le 10^5$。

代码解析

等待更新