这道题与 CF353D Queue 比较像,但后者更难一些,可以试试看。
题意简述
给定一个字符串 。使所有字母 都在左边时最少交换几次。
解题思路
当然可以枚举每个字母 的情况,但显然会超时。
仔细想一想,每个字母 到达其最左边的交换次数其实就是它前面 字母的个数。
于是就 AC 了。 时间复杂度 。
哦对了,你还要开 long long
。
代码实现
#include<bits/stdc++.h>
using namespace std;
string str; long long sum_b,ans;
int main() {
cin>>str;
for(int i=0;i<str.size();i++) {
if(str[i]=='B') sum_b++;
if(str[i]=='W') ans+=sum_b;
}
printf("%lld",ans);
return 0;
}
//code by TheCedar