首页 > 代码库 > coderforces719b
coderforces719b
题目大意：给定一个字符串，这个字符串中只有“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 100005using namespace std;char str[MAX_SIZE];int main() { int n = 0; int rn = 0, bn = 0; int cnt = 0; cin>>n; cin>>str;//rbrb switch to brbr，相当于把字符串变成brbr的形式 for(int i = 0; i < n; i++) { if(i%2 == 0) { if(str[i] == ‘r‘) rn++; } if(i%2 == 1) { if(str[i] == ‘b‘) bn++; } } cnt = max(rn,bn);//brbr switch to rbrb,相当于把字符串变成rbrb的形式 rn = bn = 0; for(int i = 0; i < n; i++) { if(i%2 == 1) { if(str[i] == ‘r‘) rn++; } if(i%2 == 0) { if(str[i] == ‘b‘) bn++; } } cout<<min(cnt,max(rn,bn))<<endl; }
coderforces719b
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。