[题解] Codeforces Global Round 22 1738 A B C D E F 题解
很久没rated打过cf的比赛了,这次打得还行,至少进前100了
点我看题
A. Glory Addicts把类型0的数放进数组a里,类型1的数放进数组b里 。如果\(|a|=|b|\),你可以把所有数里最小的放在第一个,其他的交错排列,这样除了最小的其他都能取到2的系数 。这个需要特判 。否则假设\(|a|>|b|\),则可以把a中最小的放第一个,然后分别把b和a中最大的\(|b|\)个拿出来交替排列,这样能使b和a中最大的\(|b|\)个都取到2的系数 。容易发现没有更好的排法了 。
【[题解] Codeforces Global Round 22 1738 A B C D E F 题解】时间复杂度\(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;}
经验总结扩展阅读
- 基础&进阶 线段树学习笔记(一) | P3372 【模板】线段树 1 题解
- 移动端touch拖动事件和click事件冲突问题解决
- LOL英雄联盟进入游戏无限崩溃问题解决方法?
- 常见蓝牙耳机问题解决方案 蓝牙耳机有一个连不上
- iPhone手机网络连接问题解决办法 苹果手机早上自动连接wifi怎么关
- iPhone换屏常见问题解析 苹果x换了外屏为什么没有原彩显示了
- GOA是什么
- 问题解决的过程包括哪四个阶段
- 问题解决的特点是
- 欧莱雅 【海归求职网CareerGlobal】欧莱雅资深顾问带你了解如何求职高大上的美妆行业!