浙江龙网

  1. 首页 > 生活百科 > >

[题解] Codeforces Global Round 22 1738 A B C D E F 题解

生活百科CodeforcesGl

很久没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;}

    推荐阅读


    上一篇：vue3 自定义指令控制按钮权限

    下一篇：集合框架——LinkedList集合源码分析