首页 > 代码库 > CodeForces 719B Anatoly and Cockroaches 思维锻炼题
CodeForces 719B Anatoly and Cockroaches 思维锻炼题
题目大意：有一排蟑螂，只有r和b两种颜色，你可以交换任意两只蟑螂的位置，或涂改一个蟑螂的颜色，使其变成r和b交互排列的形式。问做少的操作次数。
题目思路：更改后的队列只有两种形式：长度为n以r开头；长度为n以b开头。与初始串进行比较并统计改变次数记作ans，算出必须进行的涂色操作的次数step，我们可以把交换两只不同颜色的蟑螂的位置看做进行了两次涂改操作，其次数为（ans-step）。
那么得出改变为模板串的最小操作次数为：step+(ans-step)/2;
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<stdio.h>#include<stdlib.h>#include<queue>#include<math.h>#include<map>#define INF 0x3f3f3f3f#define MAX 1000005#define Temp 1000000000using namespace std;char str[MAX],t[MAX];int change(int n,int k){ int op=k,rsum=0,bsum=0,r,b,ans=0; for(int i=0;i<n;i++)//获取模板串 { if(op==1) t[i]=‘r‘; else t[i]=‘b‘; op*=-1; } for(int i=0;i<n;i++)//统计初始串r，b的数目，和模板串相较于初始串的改变次数 { if(str[i]==‘r‘) rsum++; else bsum++; if(str[i]!=t[i]) ans++; } if(k==1) { if(n%2==0) { r=n/2; b=n/2; } else { r=n/2+1; b=n/2; } } else if(k==-1) { if(n%2==0) { r=n/2; b=n/2; } else { r=n/2; b=n/2+1; } } int step=abs(r-rsum);//必须的涂色操作的次数 ans=step+(ans-step)/2; return ans;}int main(){ int n; while(scanf("%d",&n)!=EOF) { scanf("%s",str); int k1=change(n,1); int k2=change(n,-1); int ans=min(k1,k2); printf("%d\n",ans); } return 0;}
CodeForces 719B Anatoly and Cockroaches 思维锻炼题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。