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
4 2 1 3
3
2
3
4
Sample Output
7
9
-1
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 1000010
using 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
",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
",ans);
}
return 0;
}