Codeforces 719B Anatoly and Cockroaches(元素的交叉排列问题)

时间:2023-03-09 03:54:13
Codeforces 719B Anatoly and Cockroaches(元素的交叉排列问题)

题目链接:http://codeforces.com/problemset/problem/719/B

题目大意:

  有一队蟑螂用字符串表示,有黑色 ‘b’ 和红色 'r' 两种颜色,你想使这队蟑螂颜色分布是交叉的,你有两种做法:

    一次调整任意两个交换位置,或者一次给一个蟑螂染色

  问,最少操作多少次可以使得蟑螂的颜色分布是交叉的。

解题思路:

  刚看完题,就想到用一个字符接受第一个蟑螂的颜色【下标从0开始】,for 如果 是奇数则 应该与第一蟑螂的颜色不同,如果相同 ++c1,如果是偶数,就应该与第一个蟑螂的颜色相同,否则++c2。然后找 max(c1,c2)-》c1 要与 c2相匹配的次数+剩余的部分是用燃料涂色的次数,即找到c1 c2中的最大值即可。

  说了这么多可惜上面的思路只是对了一大半。0.o

  如果按照上面的思路,操作的次数要取决于第一个字符,如果【修改第一个比按第一个计算存在更少的情况,答案就会出问题】,解决方法:自定义第一元素【存在两种可能 ‘r’ ‘b’ 】,然后按照上面的方法从第一元素比较(下标 0),得到结果,将两种结果找到一较小值即是最终答案。

AC Code:

 #include<bits/stdC++.h>
using namespace std;
char ca[];
int solve(char c,int n)
{
int c1=,c2=;
for(int i=; i<n; i++)
{
if(c=='r')
{
if(i&&&ca[i]!='r')
++c1;
else if((!(i&))&&ca[i]!='b')
++c2;
}
else
{
if(i&&&ca[i]!='b')
++c1;
else if((!(i&))&&ca[i]!='r')
++c2;
}
}
return max(c1,c2);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",ca);
cout<<min(solve('r',n),solve('b',n))<<endl;
}
return ;
}