首页 > 代码库 > Codeforces 719B

Codeforces 719B

题意:给出一串包含‘r‘和‘b‘的字符串,每次可以把r和b的位置互换,或者改变b为r,或变r为b,求最后能成为r,b间隔序列的操作的最少次数

30分钟内没什么正确方向,理解题解后,感觉,好巧妙的思维,可能是我想不到吧。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int n;
 6 char s[100005];
 7 int main()
 8 {
 9     while(~scanf("%d",&n))
10     {
11         int xr,yr,xb,yb;
12         xr=yr=xb=yb=0;
13         scanf("%s",&s);
14         for(int i=0;i<n;i++)
15         {
16             if(i%2)
17             {
18                 if(s[i]==r)xr++;  //奇数位r的数量
19                 else xb++;      //奇数位b的数量
20             }
21             else if(s[i]==r)yr++; //偶数位r的数量
22             else yb++;          //偶数位b的数量
23         }
24         int ans=min(max(xr,yb),max(yr,xb));  
25 cout<<ans<<endl;
26     //max(xr,yb):为了转换成"brbr..."需要的最少次数
27     //只有xr和yb需要交换,而max取最大的,多出来的就只能染色了,所以能保证执行步数最少 28 } 29 return 0; 30 }

 

Codeforces 719B