CF1370 D.Odd-Even-Subsequence【二分】

题目链接：codeforces 1370D

题解

二分答案，每次check构造两个序列，枚举答案 x 是从奇数中取得还是偶数中取得。取两个序列长度的最大值 len，即只要有一个序列长度满足条件 len >= k，说明长度还可以再短，答案还可以更小。

参考代码

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
37
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, k;
bool check(int x, int len1 = 0, int len2 = 0) { // check 最小值是从奇数还是偶数得到
    for (int i = 1; i <= n; i++) { // 构造一个序列，取符合条件的奇数，偶数随意取
        if (!(len1&1)) {
            len1++;
        } else if (a[i] <= x) {
            len1++;
        }
    }
    for (int i = 1; i <= n; i++) { // 构造一序列，取符合条件的偶数，奇数随意取
        if (len2&1){
            len2++;
        } else if (a[i] <= x) {
            len2++;
        }
    }
    return max(len1, len2) >= k; // 取两者最大值，即只要有一个序列满足就可以继续缩小
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = 1e9, mid;
    while (l < r) {
        mid = (l+r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}