「BZOJ3721」PA2014 Final Bazarek
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
题解
贪心
显然排序后取最大的K个。。。但如果这K个和为偶数，就考虑将其中的一个偶数换奇数/奇数换偶数，那么只要维护下前i个中的奇数最小值和偶数最小值，后i个中奇数最大值和偶数最大值就能O1回答询问了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long #define inf 2000000000 #define mod 1000000007 using namespace std; inline 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; } int mn1[1000005],mn2[1000005],mx1[1000005],mx2[1000005]; int n,m,K; int a[1000005]; ll sum[1000005]; bool cmp(int x,int y) { return x>y; } int main() { mn1[0]=mn2[0]=inf; n=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; for(int i=1;i<=n;i++) { mn1[i]=mn1[i-1]; mn2[i]=mn2[i-1]; if(a[i]&1)mn1[i]=min(mn1[i],a[i]); else mn2[i]=min(mn2[i],a[i]); } for(int i=n;i;i--) { mx1[i]=mx1[i+1]; mx2[i]=mx2[i+1]; if(a[i]&1)mx1[i]=max(mx1[i],a[i]); else mx2[i]=max(mx2[i],a[i]); } m=read(); for(int i=1;i<=m;i++) { int K=read(); if(sum[K]&1)printf("%lld\n",sum[K]); else { ll ans=-1; if(mn1[K]!=inf&&mx2[K+1])ans=max(ans,sum[K]-mn1[K]+mx2[K+1]); if(mn2[K]!=inf&&mx1[K+1])ans=max(ans,sum[K]-mn2[K]+mx1[K+1]); printf("%lld\n",ans); } } return 0; } |
Subscribe
计数器 9858719
OI 课件=>
OI 课件=>