bzoj 3721: PA2014 Final Bazarek 贪心

如果没有限制，直接取前 $k$ 大即可.

有限制，则只有几种可能：奇换偶，偶换奇.

维护奇数偶数的前缀最小值和后缀最大值即可.

code:

#include <bits/stdc++.h>

#define N 1000005

#define LL long long

#define inf 2000000000

using namespace std;

namespace IO

{

    char *p1,*p2,buf[100000];

    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

    int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}

};

void setIO(string s)

{

    string in=s+".in";

    freopen(in.c_str(),"r",stdin);

}

LL a[N],f0[N],f1[N],g0[N],g1[N],sum[N];

bool cmp(LL a,LL b) { return a>b; }

int main()

{

    // setIO("input");

    int n,i,j,m;

    scanf("%d",&n);

    for(i=1;i<=n;++i) a[i]=(LL)IO::rd();

    sort(a+1,a+1+n,cmp);

    f0[0]=f1[0]=inf;

    for(i=1;i<=n;++i)

    {

        sum[i]=sum[i-1]+a[i];

        f0[i]=f0[i-1],f1[i]=f1[i-1];

        if(a[i]%2==0) f0[i]=a[i];

        else f1[i]=a[i];

    }

    g0[n]=g1[n]=-inf;

    for(i=n-1;i>=1;--i)

    {

        g0[i]=g0[i+1],g1[i]=g1[i+1];

        if(a[i+1]%2==0) g0[i]=a[i+1];

        else g1[i]=a[i+1];

    }

    m=IO::rd();

    for(i=1;i<=m;++i)

    {

        int k;

        k=IO::rd();

        if(sum[k]&1) printf("%lld\n",sum[k]);

        else

        {

            LL ans=0ll;

            if(f0[k]!=inf&&g1[k]!=-inf) ans=max(ans,sum[k]-f0[k]+g1[k]);

            if(f1[k]!=inf&&g0[k]!=-inf) ans=max(ans,sum[k]-f1[k]+g0[k]);

            if(!ans) printf("-1\n");

            else printf("%lld\n",ans);

        }

    }

    return 0;

}