Maximiza tu Balance#11860
Autor del Problema: | TheSensei |
Preparado por: | Hasan Saleh (MathModel) |
Editado por: | Hasan Saleh (MathModel) |
Solución Nuestro objetivo es maximizar el valor de la expresión, nota que para cada con s_i=\mathtt{B}, contribuye con -a_i a la expresión y s_i=\mathtt{S} (Vender) contribuye con a_i a la suma, así que queremos maximizar los valores de y minimizar los valores de . Tenemos exactamente dos casos:
Tenemos s_i=\mathtt{B} para todos o s_i=\mathtt{S} para todos , lo que implica que no podemos hacer ningún intercambio útil, así que calculamos la expresión tal como está.
Tenemos tanto como en , entonces queremos reducir el valor máximo de a_i con s_i=\mathtt{B} porque contribuye con un valor negativo. Un enfoque greedy es intercambiar el valor máximo de a_i con s_i=\mathtt{B} con el valor mínimo de a_i de , así tenemos una suma mayor y esta es la mejor solución.
#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;
}Complejidad