D. Odd-Even Subsequence

https://codeforces.com/contest/1370/problem/D

題意：給定一個序列，讓我們找一個大小為k的序列，求最小值

　　　最小值的定義為：min(奇數位置上的最大，偶數位置上的最小)

思路：二分

　　　對于check部分，我們分為兩塊來寫，奇數位和偶數位

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+10;
 4 int a[maxn];
 5 int n,k;
 6 int limitodd,limiteven;
 7 int check(int mid)
 8 {
 9     //先看奇數；
10     int flag=1;
11     int numodd=0;
12     int numeven=0;
13     for(int i=1;i<=n;i++){
14         if(flag==1){
15             if(a[i]<=mid){
16                 numodd++;
17                 flag=0;
18             }
19         }
20         else{
21             numeven++;
22             flag=1;
23         }
24     }
25     if(numodd>=limitodd&&numeven>=limiteven) return 1;
26     else{
27         numodd=1;
28         numeven=0;
29         flag=1;
30         for(int i=2;i<=n;i++){
31             if(flag==1){
32                 if(a[i]<=mid){
33                     numeven++;
34                     flag=0;
35                 }
36             }
37             else{
38                 numodd++;
39                 flag=1;
40             }
41         }
42         if(numodd>=limitodd&&numeven>=limiteven) return 1;
43         else return 0;
44     }
45 }
46 int main()
47 {
48     scanf("%d%d",&n,&k);
49     limiteven=k/2;
50     limitodd=k/2+k%2;
51     for(int i=1;i<=n;i++)
52         scanf("%d",&a[i]);
53     int L=1,R=1e9;
54     int ans;
55     while(L<=R){
56         int mid=L+R>>1;
57         if(check(mid)){
58             ans=mid;
59             R=mid-1;
60         }
61         else L=mid+1;
62     }
63     printf("%d\n",ans);
64     return 0;
65 }      

View Code