简答题 偏难
#16999

数字移动 时间限制:3.0 s 内存限制:512.0 MB 题目描述 小 A 有一个包含 N 个正整数的序列 A = A₁ , A₂, … …A_N,序列 A…

数字移动
时间限制:3.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列 A = A₁ , A₂, … …A_N,序列 A 恰好包含成对不同的正整数。形式化地,对于任意 1 ≤ i ≤ N ,存在唯一一个 j 满足 1 ≤j≤ N, i≠ j, A_i = A_j。
小 A 希望每对相同的数字在序列中相邻,为了实现这一目的,小 A 每次操作会选择任意 i (1 ≤ i ≤ N),将当前序列的第 i 个数字移动到任意位置,并花费对应数字的体力。

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

小 A 可以执行任意次操作,但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 X,使得他能够在每次花费的体力均不超过 X 的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数 N,代表序列长度,保证 N 为偶数。
第二行包含 N 个正整数 A₁ , A₂ , · · . , A_N,代表序列 A。且对于任意 1 ≤ i ≤ N,存在唯一一个j 满足1 ≤ j ≤ N, i≠ j, A_i= A_j。
数据保证小 A 至少需要执行一次操作。
输出格式
输出一行,代表满足要求的 X 的最小值。
样例
输入样例

6
1  2  1  3  2  3

输出样例

1

仅移动数值1即可完成全部配对,所有操作体力≤1,最小X=1。 数据范围 对于40%的测试点,保证 1 ≤ N, A_i ≤ 100。 对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false;"># 输入n和a数组 n = int(input()) a = [] while len(a) &lt; n:     a.extend(map(int, input().split())) # 答案的上下界 left, right = 0, 1000000 ans = 1000000 # 二分搜索 while left &lt;= right:     # 考虑mid的力气能否完成任务     mid = (left + right) // 2     # 筛选出所有大于mid的数字     b = [x for x in a if x &gt; mid]     # 先假设能够完成任务     possible = True     for i in range(0, len(b), 2):         # 如果两个相同且大于mid的数字 ,中间还有其它的大于mid的数字 ,则本任务无法完成         # 以 (1  2  1  3)为例 ,两个1之间存在2。假设最大只能挪动1 ,则不论如何两个1之间的2不会被挪动,最终无法完成配对         if b[i] != b[i+1]:             possible = False             break     # 如果能够成功 ,则尝试更小的mid     if possible:         ans = mid         right = mid - 1     else:         left = mid + 1 print(ans)</pre>
这道题暂未补解析。