首页 > 代码库 > bzoj3721 [PA2014 Final] Bazarek

bzoj3721 [PA2014 Final] Bazarek

2024-08-03 22:06:58   218人阅读

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
 
要求答案是奇数的01背包，并且体积为1
首先考虑去掉奇数的限制，那么很显然从大到小排序完贪心就好了
如果加上了奇数的限制，那么需要在上面的基础上做调整
如果答案就是奇数，那么不作任何处理。
如果答案是偶数，我们可以通过把集合中一个奇数换成偶数，或者一个偶数换成奇数来使得答案变成奇数。
于是只要用前缀和、保存前k个中的最小奇数/偶数、保存后k个中的最大奇数/偶数，每次可以O(1)出解。
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 1000000000000000ll#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971#define N 1000010using namespace std;int n,m;LL a[N];LL sum[N];LL mno[N],mne[N],mxo[N],mxe[N];inline LL read(){    LL 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;}int main(){	n=read();	for (int i=1;i<=n;i++)a[i]=read();	sort(a+1,a+n+1,greater<LL>());	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];	mxo[n+1]=mxe[n+1]=-inf;	mno[0]=mne[0]=inf;	for(int i=1;i<=n;i++)	{		mne[i]=mne[i-1];mno[i]=mno[i-1];		if (a[i]&1)mne[i]=min(mne[i],a[i]);		else mno[i]=min(mno[i],a[i]);	}	for (int i=n;i>=1;i--)	{		mxe[i]=mxe[i+1];mxo[i]=mxo[i+1];		if (a[i]&1)mxe[i]=max(mxe[i],a[i]);		else mxo[i]=max(mxo[i],a[i]);	}	m=read();	for (int i=1;i<=m;i++)	{		int q=read();		if (sum[q]&1)		{			printf("%lld\n",sum[q]);			continue;		}		LL ans=-1;		if(mno[q]!=inf&&mxe[q+1]!=-inf) ans=max(ans,sum[q]-mno[q]+mxe[q+1]);		if(mne[q]!=inf&&mxo[q+1]!=-inf) ans=max(ans,sum[q]-mne[q]+mxo[q+1]);		printf("%lld\n",ans);	}	return 0;}

　　

bzoj3721 [PA2014 Final] Bazarek


联系
我们