题解：CF1738A Glory Addicts

Monkey__King · 2024-05-12 22:18:02 · 题解

题意

英雄可以使用两种技能（火与冰） a_i，每个技能的初始值为 b_i。

• 如果上一个技能和当前技能都为火（或者冰），攻击值加上当前技能的初始值。
• 如果上一个技能不同于当前技能，攻击值加上当前技能的初始值乘二。

分析

我们可以分别用 t0 和 t1 来表示两种技能的个数，分类讨论：

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    cin>>T;
    while(T--){
        int n,a[100005]={0},b,s0[100005]={0},s1[100005]={0},t0=0,t1=0;
        long long ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>b;
            if(!a[i]) s0[++t0]=b;
            else s1[++t1]=b;
        }
        sort(s0+1,s0+t0+1);
        sort(s1+1,s1+t1+1);
        if(t0<t1){
            for(int i=1;i<=(t1-t0);i++) ans+=s1[i];
            for(int i=1,j=(t1-t0)+1;i<=t0;i++,j++) ans+=(s1[j]+s0[i])*2;
        }
        else if(t0>t1){
            for(int i=1;i<=(t0-t1);i++) ans+=s0[i];
            for(int i=1,j=(t0-t1)+1;i<=t1;i++,j++) ans+=(s0[j]+s1[i])*2;
        }
        else{
            if(s0[1]<s1[1]) ans+=s0[1]+s1[1]*2;
            else ans+=s1[1]+s0[1]*2;
            for(int i=2;i<=t0;i++) ans+=(s0[i]+s1[i])*2;
        }
        cout<<ans<<endl;
    }
    return 0; 
}

然而 TLE。

首先想到循环次数太多，简化可将

if(t0<t1){
    for(int i=1;i<=(t1-t0);i++) ans+=s1[i];
    for(int i=1,j=(t1-t0)+1;i<=t0;i++,j++) ans+=(s1[j]+s0[i])*2;
}
else if(t0>t1){
    for(int i=1;i<=(t0-t1);i++) ans+=s0[i];
    for(int i=1,j=(t0-t1)+1;i<=t1;i++,j++) ans+=(s0[j]+s1[i])*2;
}
else{
    if(s0[1]<s1[1]) ans+=s0[1]+s1[1]*2;
    else ans+=s1[1]+s0[1]*2;
    for(int i=2;i<=t0;i++) ans+=(s0[i]+s1[i])*2;
}
cout<<ans<<endl;

改为

for(int i=1;i<=max(t0,t1);i++){
    if(i<=t0) ans+=s0[i];
    if(i<=t1) ans+=s1[i];
    if(i<=min(t0,t1)) ans+=s0[i]+s1[i];
}
if(t0==t1) ans-=min(s0[t0],s1[t1]);
cout<<ans<<endl;

同时 sort(begin,end) 添加成 sort(begin,end,cmp) 使其降序排序。

然而还是 TLE。

尝试使用

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

来加速流输入输出的速度。

然而仍旧是 TLE。

问题在于int n,a[100005]={0},b,s0[100005]={0},s1[100005]={0},t0=0,t1=0;变量申请过大，并且为局部变量，导致查询过慢，电脑卡住了，时间超限。

把这一串变量设置为全局变量，并且在每一次循环的时候赋一遍初始值就可以了。

AC Code

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
int T;
int n,a[100005]={0},b,s0[100005]={0},s1[100005]={0},t0=0,t1=0;//申请全局变量
long long ans=0;
bool cmp(int x,int y){
    return x>y;
}//降序排序
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);//流输入输出加速。
    cin>>T;
    while(T--){
        ans=0;
        t0=0;
        t1=0;//赋值初始值为0
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>b;
            if(!a[i]) s0[++t0]=b;
            else s1[++t1]=b;
        }
        sort(s0+1,s0+t0+1,cmp);
        sort(s1+1,s1+t1+1,cmp);//排序
        for(int i=1;i<=max(t0,t1);i++){
            if(i<=t0) ans+=s0[i];
            if(i<=t1) ans+=s1[i];
            if(i<=min(t0,t1)) ans+=s0[i]+s1[i];//分类讨论
        }
        if(t0==t1) ans-=min(s0[t0],s1[t1]);//特判
        cout<<ans<<endl;
    }
    return 0; 
}

END