-
知识点:二分
-
最后需要付的是且分别为所选序列的最大值。
考虑二分最后的值,由于均为对应序列的最大值,故只要其中有一个序列存在所有的值均,即存在合法方案。
考虑对于奇数序列,偶数序列分开检查。(假定此时二分检查的值为)
对于奇数序列, 检查是否能在整个序列中找到一个⻓度为的序列,使得这个序列的所有奇数下标的值均 , 遍历整个序列,如果一个值选定作为奇数, 则下一个奇数下标至少应该在处,故遍历整个序列检查是否有的序列满足奇数位置均即可。
对于偶数序列,同理遍历整个序列检查是否有的序列满足奇数位置均即可。( 不可能作为偶数序列中的值,从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; }