U535982 J-A 小梦的AB交换 题解
小梦的AB交换小梦的AB交换 标题链接
一道字符串贪婪的题，可以先暴力求出 N<=3的情况（纸上模仿一遍就行）
正解具体解释:
思路:有两种可能 1.ABABAB… 2.BABABA…
根据标题我们需要求出最少进行的操作次数，我们需要统计有多少字符是不相当的,再用总的不相当个数除以每两个交换的数目,即可得到相应交换次数
废话不多说，上代码！
//暴力写法 45pts
// #include<bits/stdc++.h>
// using namespace std;
// int main()
// {
// int t = 1;cin>>t;
// int n;cin>>n;
// if(n == 1)cout<<0<<"\n";
// if(n == 2)cout<<1<<"\n";
// if(n == 3)cout<<1<<"\n";
// return 0;
// }
//思路:有两种可能 1.ABABAB...2.BABABA...
//根据题目我们需要求出最少进行的操作次数，我们需要统计有多少字符是不相等的,再用总的不相等个数除以每两个交换的数量
//即可得到相应交换次数
#include<bits/stdc++.h>
using namespace std;
int jisuan(string &s,string &substr1)
{
int ans = 0;
for(int i = 0;i < s.size();i++)
{
if(s != substr1)
{
ans += 1;
}
}
return ans / 2;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;cin>>t;
string a,b,s;
while(t--)
{
int n;cin>>n;
cin>>s;
for(int i = 1;i <= n * 2;i++)
{
if(i % 2 == 0)
{
a += 'A';
b += 'B';
}else
{
a += 'B';
b += 'A';
}
}
cout<< min(jisuan(s,a),jisuan(s,b))<<"\n";
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]