D. Odd-Even Subsequence
题意： 对于数列 a , 找出数列的子序列 s , 使得 $min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$ 最小。
input
output
首先，奇偶交替是一定的，所以可以选择一个奇下标元素后再选择偶的。
假定最小元素在奇序列中，
二分答案，遍历原序列 a，观察是否可以组成长度 > k 满足所有元素都小于 x 的子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| int n,k,a[MAX],l=INF,r=0,ans;
bool f(int x,int flag){
int cnt=0;
fi(i,0,n){
if(flag){
cnt ++;
flag = 0;
}else {
if(a[i]<=x){
cnt ++;
flag=1;
}
}
}
return cnt >= k;
}
int main(){
sf(n);sf(k);
fi(i,0,n) {
sf(a[i]);
l = min(l,a[i]);
r = max(r,a[i]);
}
while(l<=r){
int m = (l+r)/2;
if(f(m,0) || f(m,1)){
ans = m;
r = m-1;
}else {
l = m+1;
}
}
pf(ans);
return 0;
}
|