1054. ComistryMo的拉面店 - 帖子

知识点：二分

最后需要付的是且分别为所选序列的最大值。

考虑二分最后的值，由于均为对应序列的最大值，故只要其中有一个序列存在所有的值均，即存在合法方案。

考虑对于奇数序列，偶数序列分开检查。(假定此时二分检查的值为)

对于奇数序列, 检查是否能在整个序列中找到一个⻓度为的序列，使得这个序列的所有奇数下标的值均 , 遍历整个序列，如果一个值选定作为奇数, 则下一个奇数下标至少应该在处，故遍历整个序列检查是否有的序列满足奇数位置均即可。

对于偶数序列，同理遍历整个序列检查是否有的序列满足奇数位置均即可。( 不可能作为偶数序列中的值，从2开始检查即可)。

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
int n, k, a[N];
bool check2(int val, int z) {
    int cnt = 0;
    if (z == 0) {  // 奇数序列是否满⾜
        for (int i = 1; i <= n; i++) {
            if (a[i] <= val) {
                if (i != n)
                    cnt += 2;
                else
                    cnt++;
                i++;
            }
        }
    } else {  //偶数序列是否满⾜
        cnt++;
        for (int i = 2; i <= n; i++) {
            if (a[i] <= val) {
                if (i != n)
                    cnt += 2;
                else
                    cnt++;
                i++;
            }
        }
    }
    return cnt >= k;  // 判断最终满⾜条件的序列⻓度是否 >= k
}
bool check(int val) {
    if (check2(val, 0) || check2(val, 1))
        return true;
    return false;
}
void solve() {
    cin >> n >> k;
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        r = max(r, a[i]);
    }
    while (l != r - 1) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}