很久没rated打过cf的比赛了 ， 这次打得还行，至少进前100了
【[题解] Codeforces Global Round 22 1738 A B C D E F 题解】点我看题
A. Glory Addicts把类型0的数放进数组a里 ， 类型1的数放进数组b里 。如果\(|a|=|b|\) ， 你可以把所有数里最小的放在第一个，其他的交错排列，这样除了最小的其他都能取到2的系数 。这个需要特判 。否则假设\(|a|>|b|\)，则可以把a中最小的放第一个，然后分别把b和a中最大的\(|b|\)个拿出来交替排列，这样能使b和a中最大的\(|b|\)个都取到2的系数 。容易发现没有更好的排法了 。
时间复杂度\(O(nlogn)\) 。
点击查看代码#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backusing namespace std;LL t,n,tt[100010],vv[100010];vector <LL> a,b;int main(){ cin>>t; rep(tn,t) { scanf("%lld",&n); a.clear();b.clear(); rep(i,n) scanf("%lld",&tt[i]); rep(i,n) scanf("%lld",&vv[i]); LL ans=0; LL mn=1e18; rep(i,n) { if(tt[i]==0) a.pb(vv[i]);else b.pb(vv[i]); ans+=vv[i]; mn=min(mn,vv[i]); } sort(a.begin(),a.end());reverse(a.begin(),a.end()); sort(b.begin(),b.end());reverse(b.begin(),b.end()); if(a.size()==b.size()) { printf("%lld\n",ans*2-mn); continue; } LL sz=min(a.size(),b.size()),v1=0,v2=0; rep(i,sz) v1+=a[i];rep(i,sz) v1+=b[i]; ans+=v1; printf("%lld\n",ans); } return 0;}
推荐阅读
-
2023年大年初四十二生肖运势 运气最佳生肖是什么？
-
-
-
在美国并不是所有的州都庆祝哥伦布纪念日 哥伦布纪念日如何庆祝
-
武汉非机动车牌照补办需要哪些前提 武汉非机动车牌照补办需要哪些前提材料
-
-
-
-
-
-
-
如何创建网页快捷方式到桌面，如何将网页以快捷方式保存在桌面？
-
-
雅鲁藏布江大峡谷产生的原因 雅鲁藏布江大峡谷产生的原因
-
-
怎样修改路由器wifi密码 192.168.11路由器设置教程
-
-
-
关于海因茨·弗洛赫简述 海因茨·弗洛赫
-
