二分算法

题意：移动序列中的数字，使序列中每对相等的数相邻，每次移动消耗体力为移动数的数值大小。
求一个最小的值x，使得每次花费的体力不超过x并达成要求的目标。

分析：每次花费的体力不超过x，即只允许移动小于等于x的数，考虑把它们都移到一边，剩下的就是不能移动的数。
此时如果可以达成 “序列中每对相等的数相邻”的目标，则不能移动的数必须保证相邻相等。

不能移动的数要保持先后顺序，因此可以考虑将大于x的数重新组合成一个序列，去进行判断。

1<=Ai<=10^5，如果采用暴力枚举的方法，显然会超时。
比较容易想到的：如果 x 作为答案可行那么对于任意 y≥x 都可行，有单调性，考虑二分算法。
典型二分答案题，依次计算中间值进行检验即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n, a[N], L=1, R=1, mid, ans; 
bool check(int x){
	vector<int> vt;
	for(int i=1; i<=n; i++){
		if(a[i]>x) vt.push_back(a[i]);
	}
	for(int i=1; i<vt.size(); i+=2){
		if(vt[i]!=vt[i-1]) return false;
	}
	return true;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
		R=max(R, a[i]);
	}
	while(L<=R){
		mid=(L+R)/2;
		if(check(mid)){
			ans=mid;
			R=mid-1;
		}else L=mid+1;
	}
	cout<<ans;
	return 0;
}