Maximize your Balance#11860

Maximize your Balance (Çözgüdiň düşündirişi)

Problem Author:	TheSensei
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution Our goal is to maximize the value of the expression notice that for each $i$ with $s_{i} = B$ s_i=\mathtt{B} then it contributes with $- a_{i}$ -a_i to expression and $s_{i} = S$ s_i=\mathtt{S} (Sell) contributes with $a_{i}$ a_i to sum , thus we want to maximize the values of $S$ and minimize values of $B$ , We've exactly two cases :

We've $s_{i} = B$ s_i=\mathtt{B} for all $i$ or $s_{i} = S$ s_i=\mathtt{S} for all $i$ , which implies that we cannot do any useful swap , so we calculate the expression as it's
We've both $B$ and $S$ appears in $s$ , then we want to reduce the max value of $a_{i}$ a_i with $s_{i} = B$ s_i=\mathtt{B} because it's contributes with negative value , A greedy approach is to swap the max value of $a_{i}$ a_i with $s_{i} = B$ s_i=\mathtt{B} with min value of $a_{i}$ a_i of $S$ thus we've a larger sum and this is the best 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;
}

C++

Complexity $O (n)$