[CF] #651 D. Odd-Even Subsequence

Codeforces Round #651 (Div. 2)

题意：

给定一个序列，定义它的子序列为：删除中部分元素，且其余元素的顺序不变。同时新序列的花费为，其序列为奇数的所有元素的最大值和序列为偶数的所有元素的最大值的最小值，既最小花费为，现给定一个长度为的序列，问其长度为的子序列的最小花费是多少。

分析：

对答案二分，可以发现如果答案如果比我们当前二分的值要小，那么子序列长度一定是大于答案的子序列的，同理，如果答案比我们当前二分的值要大，那么我们构建的子序列一定会更短。那问题的关键就变成了如何去当前值的序列长度，和进行比较。由于题目要求奇偶序列中的最大值的最小值，那么也就是说，只要序列号为奇数或者为偶数其中一个的最大值小于等于答案，那么这个序列就一定可以被构建出来，而不需要考虑另外一个。因此我们只需要贪心的构建奇数或者偶数序列，就可以得到一个花费为当前值的长度为的序列，和进行比较就可以实现二分的。

代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 +7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int num[MAXNe6], n, k;
bool check(int x, int pos) {
    int ans = 0;
    for(int i = 1; i <= n; ++ i) {
        if(pos) {
            ans ++;
            pos ^= 1;
        } else if(num[i] <= x) {
            ans ++;
            pos ^= 1;
        }

    }
    return ans >= k;
}
int main() {
    n = read(), k = read();
    for(int i = 1; i <= n; ++ i) num[i] = read();
    int l = 1, r = mod;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid, 0) || check(mid, 1)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}