U535982 J-A 小梦的AB交换 题解

小梦的AB交换

小梦的AB交换 标题链接
一道字符串贪婪的题，可以先暴力求出 N<=3的情况（纸上模仿一遍就行）
正解具体解释:
思路:有两种可能 1.ABABAB… 2.BABABA…
根据标题我们需要求出最少进行的操作次数，我们需要统计有多少字符是不相当的,再用总的不相当个数除以每两个交换的数目,即可得到相应交换次数
废话不多说，上代码！

1. //暴力写法 45pts
2. // #include<bits/stdc++.h>
3. // using namespace std;
4. // int main()
5. // {
6. //     int t = 1;cin>>t;
7. //     int n;cin>>n;
8. //     if(n == 1)cout<<0<<"\n";
9. //     if(n == 2)cout<<1<<"\n";
10. //     if(n == 3)cout<<1<<"\n";
12. //     return 0;
13. // }
16. //思路:有两种可能 1.ABABAB...  2.BABABA...
17. //根据题目我们需要求出最少进行的操作次数，我们需要统计有多少字符是不相等的,再用总的不相等个数除以每两个交换的数量
18. //即可得到相应交换次数
19. #include<bits/stdc++.h>
20. using namespace std;
21. int jisuan(string &s,string &substr1)
22. {
23.     int ans = 0;
24.     for(int i = 0;i < s.size();i++)
25.     {
26.         if(s[i] != substr1[i])
27.         {
28.             ans += 1;
29.         }
30.     }
31.     return ans / 2;
32. }
33. int main()
34. {
35.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
36.     int t;cin>>t;
37.     string a,b,s;
38.     while(t--)
39.     {
40.         int n;cin>>n;
41.         cin>>s;
42.         for(int i = 1;i <= n * 2;i++)
43.         {
44.             if(i % 2 == 0)
45.             {
46.                 a += 'A';
47.                 b += 'B';
48.             }else
49.             {
50.                 a += 'B';
51.                 b += 'A';
52.             }
53.         }
54.          cout<< min(jisuan(s,a),jisuan(s,b))<<"\n";
55.     }
56.    
58.     return 0;
59. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。