Balansınızı Maksimuma Çıxarın#11860

Balansınızı Maksimuma Çıxarın (Həll təhlili)

Problem Müəllifi:	TheSensei
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Məqsədimiz ifadənin dəyərini maksimuma çatdırmaqdır, qeyd edin ki, $s_{i} = B$ s_i=\mathtt{B} olan hər $i$ ifadəyə $- a_{i}$ -a_i ilə töhfə verir və $s_{i} = S$ s_i=\mathtt{S} (Satış) isə cəmlə $a_{i}$ a_i ilə töhfə verir, beləliklə, $S$ -nin dəyərlərini maksimuma çatdırmaq və $B$ -nin dəyərlərini minimuma endirmək istəyirik. Bizim tam iki halımız var:

Bütün $i$ üçün $s_{i} = B$ s_i=\mathtt{B} və ya bütün $i$ üçün $s_{i} = S$ s_i=\mathtt{S} var, bu da faydalı dəyişdirmə edə bilməyəcəyimizi bildirir, buna görə ifadəni olduğu kimi hesablayırıq.
Həm $B$ , həm də $S$ $s$ -də görünür, o zaman $s_{i} = B$ s_i=\mathtt{B} olan $a_{i}$ a_i-nin maksimum dəyərini azaltmaq istəyirik, çünki bu, mənfi dəyərə töhfə verir. Açgöz yanaşma, $s_{i} = B$ s_i=\mathtt{B} olan maksimum $a_{i}$ a_i-ni $S$ -nin minimum $a_{i}$ a_i ilə dəyişdirməkdir, beləliklə, daha böyük bir cəmi əldə edirik və bu, ən yaxşı həll yoludur.

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

Komplekslik $O (n)$