Maximisez votre Solde (Corrigé)

Solution Notre objectif est de maximiser la valeur de l'expression, remarquez que pour chaque $i$ avec s_i=\mathtt{B}, il contribue avec -a_i à l'expression et s_i=\mathtt{S} (Vente) contribue avec a_i à la somme, donc nous voulons maximiser les valeurs de $\mathtt{S}$ et minimiser les valeurs de $\mathtt{B}$. Nous avons exactement deux cas :

1. Nous avons s_i=\mathtt{B} pour tous les $i$ ou s_i=\mathtt{S} pour tous les $i$, ce qui implique que nous ne pouvons pas faire d'échange utile, donc nous calculons l'expression telle quelle.

2. Nous avons à la fois $\mathtt{B}$ et $\mathtt{S}$ apparaissant dans $s$, alors nous voulons réduire la valeur maximale de a_i avec s_i=\mathtt{B} car cela contribue avec une valeur négative. Une approche gloutonne consiste à échanger la valeur maximale de a_i avec s_i=\mathtt{B} avec la valeur minimale de a_i de $\mathtt{S}$, ainsi nous avons une somme plus grande et c'est la meilleure solution.

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    vector<int>a(n);
    for(auto &i:a)cin>>i;
    int mx=0;
    int mn=1e18;
    int idx1=-1,idx2=-1;
    for(int i=0;i<n;i++){
        if(s[i]=='B'){
            if(a[i]>mx){
                idx1=i;
                mx=a[i];
            }
        }
        if(s[i]=='S'){
            if(a[i]<mn){
                idx2=i;
                mn=a[i];
            }
        }
    }
    if(idx1!=-1 && idx2!=-1){
        swap(s[idx1],s[idx2]);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(s[i]=='B'){
            ans+=a[i]*-1;
        }else{
            ans+=a[i];
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Complexité $\mathcal{O}(n)$