Максимізуйте свій баланс#11860

Максимізуйте свій баланс (Розбір)

Автор проблеми:	TheSensei
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Рішення Наша мета — максимізувати значення виразу, зверніть увагу, що для кожного $i$ з $s_{i} = B$ s_i=\mathtt{B} він вносить $- a_{i}$ -a_i у вираз, а $s_{i} = S$ s_i=\mathtt{S} (Продаж) вносить $a_{i}$ a_i у суму, отже, ми хочемо максимізувати значення $S$ і мінімізувати значення $B$ . У нас є точно два випадки:

У нас $s_{i} = B$ s_i=\mathtt{B} для всіх $i$ або $s_{i} = S$ s_i=\mathtt{S} для всіх $i$ , що означає, що ми не можемо виконати жодних корисних обмінів, тому ми обчислюємо вираз як є.
У нас обидва $B$ і $S$ з'являються в $s$ , тоді ми хочемо зменшити максимальне значення $a_{i}$ a_i з $s_{i} = B$ s_i=\mathtt{B}, оскільки воно вносить негативне значення. Жадібний підхід полягає в тому, щоб поміняти максимальне значення $a_{i}$ a_i з $s_{i} = B$ s_i=\mathtt{B} з мінімальним значенням $a_{i}$ a_i з $S$ , отже, ми маємо більшу суму, і це найкраще рішення.

#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++

Складність $O (n)$