1054. ComistryMo的拉面店

new_user_2 2024-03-11 8:53:54

  • 知识点:二分

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

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

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

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

    对于偶数序列,同理遍历整个序列检查是否有的序列满足奇数位置均即可。( 不可能作为偶数序列中的值,从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;
    }