【BZOJ-3721】Final Bazarek 贪心

3721: PA2014 Final Bazarek

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 610  Solved: 243
[Submit][Status][Discuss]

Description

有n件商品，选出其中的k个，要求它们的总价为奇数，求最大可能的总价。

Input

第一行一个整数n(1<=n<=1000000)，表示商品数量。
接下来一行有n个整数，表示每件商品的价格，范围在[1,10^9]。
接下来一行有一个整数m(1<=m<=1000000)，表示询问数量。
接下来m行，每行一个整数k[i](1<=k[i]<=n)。

Output

对于每个询问，输出一行表示保证奇数的情况下最大的总价。若无法满足要求，输出-1。

Sample Input

4
4 2 1 3
3
2
3
4

Sample Output

7
9
-1

HINT

Source

鸣谢Jcvb

Solution

贪心直接搞就可以

首先我们从大到小排序，然后处理出$sumV[i]$,$maxo[i]$,$maxe[i]$,$mino[i]$,$mine[i]$

分别表示：前缀和、后缀最大奇数、后缀最大偶数、前缀最小奇数、前缀最小偶数

然后对于一次询问K，如果$sumV[K]$为奇数，那么答案显然是$sumV[K]$

如果为偶数，考虑替换，把前缀最小奇数替换成后缀最大偶数，或前缀最小偶数替换成后缀最大奇数，这样取较大即可

这样替换，显然满足sum从偶变奇，且总和最大。

特判一下不合法的情况输出-1即可。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 1000100

int N,K,M;

int val[MAXN],mine[MAXN],maxo[MAXN],mino[MAXN],maxe[MAXN];

LL sumV[MAXN];

#define INF 0x7fffffff

bool cmp(int x,int y) {return x>y;}

void PreWork()

{

    sort(val+,val+N+,cmp);

    for (int i=; i<=N; i++) sumV[i]=sumV[i-]+(LL)val[i];

    mine[]=INF; mino[]=INF;

    for (int i=; i<=N; i++)

        mine[i]=min(mine[i-],val[i]&? INF:val[i]),

        mino[i]=min(mino[i-],val[i]&? val[i]:INF);

    maxo[N+]=-INF; maxe[N+]=-INF;

    for (int i=N; i>=; i--)

        maxe[i]=max(maxe[i+],val[i]&? -INF:val[i]),

        maxo[i]=max(maxo[i+],val[i]&? val[i]:-INF);

}

inline LL Ask(int K)

{

    if (sumV[K]&) return sumV[K];

    bool f1=,f2=; LL re=-INF;

    if (mino[K]!=INF && maxe[K+]!=-INF) f1=;

    if (mine[K]!=INF && maxo[K+]!=-INF) f2=;

    if (!f1 && !f2) return (LL)-;

    if (f1) re=max(re,sumV[K]-mino[K]+maxe[K+]);

    if (f2) re=max(re,sumV[K]-mine[K]+maxo[K+]);

    return re;

}

int main()

{

    N=read();

    for (int i=; i<=N; i++) val[i]=read();

    M=read();

    PreWork();

    while (M--) K=read(),printf("%lld\n",Ask(K));

    return ;

}