P14917 [GESP202512 五级] 数字移动 二分

P14917 [GESP202512 五级] 数字移动
题目的意思是通过花费i可以将数字i移动到任意位置，求需要把这个数列变成相同的数字两两相邻的，所需要的代价最大值最小。
因为看到最大值最小，我们可以往二分上面考虑，看一下答案是不是满足单调性的。
发现确实是满足单调性的，假设这个最小值是y，如果x<y的话，显然是不能完成所有的排序的；而大于等于的话就可以，所以在这里二分这个上限值。
注意题目给的ai的范围不一定是连续的，所以上界要取得ai最大值再加一。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n;
int a[N];
int b[N],c[N],cnt = 0;
bool check(int x)
{cnt = 0;for(int i = 1 ; i <= n ; ++i)if(a[i] > x)b[++cnt] = a[i];int flag = 0;for(int i = 1 ; i < cnt ; i += 2){if(b[i] != b[i+1]){flag = 1;break;}}return flag == 0;
}
int main()
{cin>>n;int mx = 0;for(int i = 1 ; i <= n ; ++i)cin>>a[i],mx = max(mx,a[i]);int l = 0,r = mx+1;while(l+1 < r){int mid = l+r>>1;if(check(mid))r = mid;else l = mid;}cout<<r<<endl;return 0;
}