coderforces719b

时间:2021-04-01 20:15:22

题目大意:给定一个字符串,这个字符串中只有“r”和"b"组成,每次操作只能交换两个字符的位置或者将一个字符由"r"变"b"(或由"b"变"r").

问:至少需要操作多少次才能使得字符串中rb依次存在(rbrbrbrb...或者brbrbrbr....)

题解:交换所需要得次数肯定是小于字符变值,所以操作中优先考虑交换,然后才考虑改变字符值.所以用两个变量(rn,bn)依次记录下与标准字符串的差值

对于每个字符串分别用brbr和rbrbrb的形式判断他们.然后每交换一次,rn与bn都要减少一次。等交换完毕,剩下的操作就是变值,所以总的操作数就是

两个变量中差值大的那个。然后从两种变换中找出值最小的那个。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define MAX_SIZE 100005
using namespace std;
char str[MAX_SIZE];
int main()
{
int n = ;
int rn = , bn = ;
int cnt = ;
cin>>n;
cin>>str;
//rbrb switch to brbr,相当于把字符串变成brbr的形式
for(int i = ; i < n; i++)
{
if(i% == )
{
if(str[i] == 'r')
rn++;
}
if(i% == )
{
if(str[i] == 'b')
bn++;
} }
cnt = max(rn,bn);
//brbr switch to rbrb,相当于把字符串变成rbrb的形式
rn = bn = ;
for(int i = ; i < n; i++)
{
if(i% == )
{
if(str[i] == 'r')
rn++;
}
if(i% == )
{
if(str[i] == 'b')
bn++;
} }
cout<<min(cnt,max(rn,bn))<<endl; }

相关文章