A21991. 数字移动
填空题
困难
知识点
题目描述
数字移动
题目描述
小A有一个包含N个正整数的序列A={A1,A2,...,Ax}，序列A恰好包含N/2对不同的正整数。形式化地，对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。
小A希望每对相同的数字在序列中相邻，为了实现这一目的，小A每次操作会选择任意i（1≤i≤N），将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。
例如，假设序列A={1,2,1,3,2,3}，小A可以选择i=2，将A2=2移动到A3=1的后面，此时序列变为{1,1,2,3,2,3}，耗费2点体力。小A也可以选择i=3，将A3=1移动到A2=2的前面，此时序列变为{1,1,2,3,2,3}，花费1点体力。
小A可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小A希望你能帮他计算出一个最小的z，使得他能够在每次花费的体力均不超过:的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数N，代表序列长度，保证N为偶数。
第二行包含N个正整数A1,A2,...,AN，代表序列A。且对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠j,Ai=Aj。
数据保证小A至少需要执行一次操作。
输出格式
输出⼀⾏，代表满⾜要求的x的最⼩值。
样例
输入样例
6
1 2 1 3 2 3输出样例
2数据范围
对于40%的测试点，保证1≤N,Ai≤100。
对于所有测试点，保证1≤N,Ai≤105。
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int pos;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
int left = 1, right = 1e6, ans = 1e6;
while(left <= right){
int mid = (left + right) / 2;
bool possible = true;
pos = 0;
for(int i = 0; i < n; i++){
if(a[i] >= mid){
b[pos++] = a[i];
}
}
for(int i = 0; i < pos; i += 2){
if(b[i] < b[i+1]){
possible = false;
break;
}
}
if(possible){
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}
上一题
下一题