P14917 [GESP202512 五级] 数字移动

题目描述

小 A 有一个包含 $N$ 个正整数的序列 A={A1,A2,⋯ ,AN}A=\{A_1,A_2,\cdots,A_N\}A={A1​,A2​,⋯,AN​}，序列 $A$ 恰好包含 $\frac{N}{2}$ 对不同的正整数。形式化地，对于任意 $1\le i\le N$，存在唯一一个 $j$ 满足 $1\le j\le N,i\ne j,A_i=A_j$。

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

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

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

输入格式

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

第二行包含 $N$ 个正整数 $A_1,A_2,\dots ,A_N$，代表序列 $A$。且对于任意 $1\le i\le N$，存在唯一一个 $j$ 满足 $1\le j\le N,i\ne j,A_i=A_j$。

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

输出格式

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

输入输出样例 #1

输入 #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$。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;	// 严格要求 (将long long 类型取别名)
ll a[1000100], b[1000100];
bool func(ll n, ll mid){
	memset(b, 0, sizeof(b));
	ll t = 1;
	for(ll i = 1; i <= n; i++){
		if(a[i] > mid){
			b[t++] = a[i];
		}
	}
	
	for(ll i = 1; i <= t - 1; i += 2){	//已经确保i不会访问到最后的元素 
		if(b[i] != b[i + 1]){
			return false;
		}
	}
	return true;
} 
int main(){
	ios :: sync_with_stdio(0);	// 提高cin、cout的运行速度
	cin.tie(0);
	cout.tie(0);
	
	ll n, maxn = -1e9;
	cin >> n;
	
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
		maxn = max(maxn, a[i]);	//输入的最大值 等一会二分要用 
	}
	
	ll l = 1, r = maxn;
	
	while(l < r){
		ll mid = (l + r) / 2;
		if(func(n, mid)){	//如果符合x要求可能就大了 
			r = mid;
		}
		else{	//否则x就可能要求小了 
			l = mid + 1;
		}
	}
	cout << l << endl;	//最后l == r 

    return 0;
}