cf 1370D. Odd-Even Subsequence (二分答案+贪心)

题目：传送门

思路：直接二分答案，O(n) check ，check时只需要保证能构造出子序列满足 x（二分的数字）在奇数序号或者偶数序号中是最大（都小于等于x）的即可，另一组直接放一个数组最大值。

　　　这是我之后基于其他人代码得到的思路，我自己一开始的思路就是分为四种情况做二分+dp：（dp用于check奇数或者偶数序号的长度）

　　　　1. k为偶数，最后的序列是 O_O_O_O_...O_ ，dp[1~n-1]

　　　　2. k为偶数，最后的序列是 _O_O_O_O..._O ，dp[2~n]

　　　　3. k为奇数，最后的序列是 O_O_O_O_...O_O ，dp[1~n]

　　　　4. k为奇数，最后的序列是 _O_O_O_..._O_ ，dp[2~n-1]

方法一：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int inf=0x3f3f3f3f;
 5 const int N=2e5+5;
 6 LL read()
 7 {
 8     LL x=0,f=1;
 9     char ch=getchar();
10     while(!isdigit(ch)){ if(ch=='-')f=-1; ch=getchar(); }
11     while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
12     return x*f;
13 }
14 int n,k,a[N];
15 bool check(int x,int flag)
16 {
17     int cnt=0;
18     for(int i=1;i<=n;i++)
19         if(flag)
20         {
21             if(a[i]<=x) flag=0,cnt++;
22         }
23         else flag=1,cnt++;
24     return cnt>=k;
25 }
26 int main()
27 {
28     scanf("%d%d",&n,&k);
29     int l=inf,r=0;
30     for(int i=1;i<=n;i++) a[i]=read(),l=min(l,a[i]),r=max(r,a[i]);
31     while(l<=r)
32     {
33         int mid=l+r>>1;
34         if(check(mid,1)||check(mid,0)) r=mid-1;
35         else l=mid+1;
36     }
37     printf("%d
",l);
38     return 0;
39 }

View Code

方法二：

#include<bits/stdc++.h>
/*
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<cctype>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
*/
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int N=3e5+5;
const int M=1e4+5;
const int inf=0x3f3f3f3f;
const LL mod=1e9+7;
const double eps=1e-9;
const long double pi=acos(-1.0L);
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
LL read()
{
    LL x=0,t=1;
    char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') t=-1;
    while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
    return x*t;
}
int a[N],f[N],n,k;

bool check(int x)
{
    if(k%2==0){
        for(int i=1;i<=n;i++) f[i]=0;
        for(int i=2;i<=n;i++)
            if(a[i]<=x) f[i]=f[i-2]+1;
            else f[i]=f[i-1];
        if(f[n]>=k/2) return 1;
        for(int i=1;i<=n;i++) f[i]=0;
        for(int i=1;i<n;i++)
            if(a[i]<=x) f[i]=f[max(i-2,0)]+1;
            else f[i]=f[i-1];
        if(f[n-1]>=k/2) return 1;
    }
    else {
        for(int i=1;i<=n;i++) f[i]=0;
        for(int i=2;i<n;i++)
            if(a[i]<=x) f[i]=f[i-2]+1;
            else f[i]=f[i-1];
        if(f[n-1]>=k/2) return 1;
        for(int i=1;i<=n;i++) f[i]=0;
        for(int i=1;i<=n;i++)
            if(a[i]<=x) f[i]=f[max(i-2,0)]+1;
            else f[i]=f[i-1];
        if(f[n]>k/2) return 1;
    }

    return 0;
}
int main()
{
    int T=1;
    while(T--)
    {
        n=read(),k=read();
        int l=inf,r=0;
        for(int i=1;i<=n;i++) a[i]=read(),r=max(a[i],r),l=min(l,a[i]);
        while(l<=r)
        {
            int mid=l+r>>1;
            if(check(mid)) r=mid-1;
            else l=mid+1;
        }
        printf("%d
",l);
    }
}

View Code