首页 > 代码库 > 【贪心】bzoj3721 PA2014 Final Bazarek

【贪心】bzoj3721 PA2014 Final Bazarek

2024-07-30 22:26:44   219人阅读

考虑不限制奇偶的情况，那就是直接排序取前k个的和。

加上奇偶限制：若排序后的前k个的和是偶数，则“显然地”：将其中的最小的奇数替换成未被选择的数中最大的偶数 或者 将其中的最小的偶数替换成未被选择的数中最大的奇数 是最优的。

那么排序之后 就可以预处理出 某个位置左侧最小的奇数、左侧最小的偶数、右侧最大的奇数、右侧最大的偶数，然后就可以O(1)地回答每个询问了。

开long long

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define N 1050001 5 typedef long long ll; 6 #define INF 2147483647 7 int n,a[N],lminj[N],lmino[N],rmaxj[N],rmaxo[N],jnow=INF,onow=INF,m,k; 8 ll sum[N]; 9 bool cmp(const int &a,const int &b){return a>b;}10 int main()11 {12     scanf("%d",&n);13     for(int i=1;i<=n;i++) scanf("%d",&a[i]);14     sort(a+1,a+n+1,cmp);15     for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(ll)a[i];16     for(int i=1;i<=n;i++)17       {18         if(a[i]&1) jnow=min(jnow,a[i]);19         else onow=min(onow,a[i]);20         lminj[i]=jnow; lmino[i]=onow;21       } jnow=onow=0;22     for(int i=n-1;i>=1;i--)23       {24         if(a[i+1]&1) jnow=max(jnow,a[i+1]);25         else onow=max(onow,a[i+1]);26         rmaxj[i]=jnow; rmaxo[i]=onow;27       }28     scanf("%d",&m);29     for(int i=1;i<=m;i++)30       {31         scanf("%d",&k);32         if(sum[k]&1) printf("%lld\n",sum[k]);33         else34           {35             ll ans=-1;36             if(lminj[k]!=INF&&rmaxo[k]!=0) ans=max(ans,sum[k]-(ll)lminj[k]+(ll)rmaxo[k]);37             if(lmino[k]!=INF&&rmaxj[k]!=0) ans=max(ans,sum[k]-(ll)lmino[k]+(ll)rmaxj[k]);38             printf("%lld\n",ans);39           }40       }41     return 0;42 }

 

【贪心】bzoj3721 PA2014 Final Bazarek


联系
我们