U535982 J-A 小梦的AB交换 - 洛谷

题目描述

小梦有一个长度为 2⋅n 的 AB 串 s，即 s 中只包含 "A" 和 "B" 两种字符，且其中恰好有 n 个 "A" 和 n 个 "B"。

他可以对 s 执行以下操作：

• 选择 i,j (1≤i,j≤2⋅n,ieqj)，并交换 si​ 和 sj​。

他想知道，需要至少多少次操作，才能使得 s 满足相邻的字符不相同，请你帮他算一算吧。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据的格式如下：

• 第一行一个正整数 n，表示 s 长度的一半。
• 第二行一个长度为 2⋅n 的字符串 s，保证只由 "A", "B" 两种字符构成。

输出格式

对于每组测试数据：

• 在单独的一行输出一个整数，表示最少进行的操作次数。

输入输出样例

​​输入 #1​​

2
1
AAABB
3
ABAABB

​​输出 #1​​

1
3

说明/提示

​​【样例1解释】​​
交换 s2​=A 和 s5​=B，得到 s="ABABAB"，满足题意，一次交换即可。

​​【数据范围】​​

• 令 N 表示 T 组数据中 n 的总和。
• 对于 50% 的数据有：T=1,1≤N≤3。
• 对于所有的测试数据有：1≤T≤100,1≤N≤10^6。

---

思路：

1. 合法形式的唯一性

最终的字符串只能是两种交替形式：

• ABABAB...：奇数位置为A，偶数位置为B。

• BABABA...：奇数位置为B，偶数位置为A。

2. 交换次数的计算逻辑

• 统计奇数位置的A数量（a_odd）：

  • 遍历字符串，统计所有1-based奇数位置上的A的数量。

  • 例如，字符串长度为6（n=3），奇数位置为1、3、5。

• 转换为ABABAB形式的交换次数：

  • 需要奇数位置全为A。当前已有a_odd个A，因此需要补充的A数量为 n - a_odd。

  • 这些A必须从偶数位置的A中交换过来，因此需要 n - a_odd 次交换。

• 转换为BABABA形式的交换次数：

  • 需要奇数位置全为B。当前奇数位置有a_odd个A需要被替换为B。

  • 因此，需要 a_odd 次交换。

• 取最小值：

  • 最终结果为 min(a_odd, n - a_odd)。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int T;
	cin >> T;
	while(T--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		int a = 0,b = 0;
		for(int i = 0 ; i < 2*n ; i++)
		{
			if(i % 2 != 0)
			{
				if(s[i] == 'A')
				{
					a++;
				}
			}
		}
		cout << min(n-a,a) << endl;
		
	}
	return 0;
 }