首页 > 代码库 > 【BZOJ-3721】Final Bazarek 贪心

【BZOJ-3721】Final Bazarek 贪心

2024-08-12 14:53:17   216人阅读

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 longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}    return x*f;}#define MAXN 1000100int N,K,M;int val[MAXN],mine[MAXN],maxo[MAXN],mino[MAXN],maxe[MAXN];LL sumV[MAXN];#define INF 0x7fffffffbool cmp(int x,int y) {return x>y;}void PreWork(){    sort(val+1,val+N+1,cmp);    for (int i=1; i<=N; i++) sumV[i]=sumV[i-1]+(LL)val[i];    mine[0]=INF; mino[0]=INF;    for (int i=1; i<=N; i++)         mine[i]=min(mine[i-1],val[i]&1? INF:val[i]),        mino[i]=min(mino[i-1],val[i]&1? val[i]:INF);    maxo[N+1]=-INF; maxe[N+1]=-INF;    for (int i=N; i>=1; i--)        maxe[i]=max(maxe[i+1],val[i]&1? -INF:val[i]),        maxo[i]=max(maxo[i+1],val[i]&1? val[i]:-INF);}inline LL Ask(int K){    if (sumV[K]&1) return sumV[K];     bool f1=0,f2=0; LL re=-INF;    if (mino[K]!=INF && maxe[K+1]!=-INF) f1=1;    if (mine[K]!=INF && maxo[K+1]!=-INF) f2=1;    if (!f1 && !f2) return (LL)-1;     if (f1) re=max(re,sumV[K]-mino[K]+maxe[K+1]);    if (f2) re=max(re,sumV[K]-mine[K]+maxo[K+1]);    return re;}int main(){    N=read();    for (int i=1; i<=N; i++) val[i]=read();    M=read();    PreWork();    while (M--) K=read(),printf("%lld\n",Ask(K));    return 0;}

【BZOJ-3721】Final Bazarek 贪心


联系
我们