📝 题目大意

给定一个由 A、B、C 组成、长度为 $N$ 的字符串 $S$。你可以进行两种操作：将 A 替换为 BB，或将相邻的 BB 替换为 A。求所有可达字符串中字典序最小的一个。

💡 解题思路

1. 题目分析：

   • $N \leq 2 \times 10^5$，需要 $O(N)$ 或 $O(N \log N)$ 的算法。
   • 操作 A ↔ BB 是可逆的，说明 A 和 BB 在某种意义下等价。
   • C 不参与任何操作，是固定的"墙壁"，将字符串分割为若干独立段。

2. 算法推导：

   • 将 A 视为 2 个"B 单位"，B 视为 1 个"B 单位"。两种操作均不改变 B 单位总数。
   • 可以证明：在相邻位置，BA 可以变为 AB（$BA \to B \cdot BB \to BBB \to AB$），即 A 和 B 可以自由交换。
   • 因此，在相邻 C 之间的每一段中，我们可以任意排列 A 和 B，且可以任意进行 A ↔ BB 的转换。唯一不变量是该段的 B 单位总数。
   • 要使字典序最小，应尽量把 A 放在前面：设某段 B 单位总数为 $cnt$，则最优排列为 $\lfloor cnt/2 \rfloor$ 个 A 后跟 $cnt \bmod 2$ 个 B（即 A 尽可能多，至多剩余一个 B）。
   • std.cpp 中的贪心实现：从左到右扫描，遇到 B 时：
     • 若下一个字符是 A，则交换二者（BA → AB），将 A 向左推，使字典序更小；
     • 若下一个字符是 B，则合并为 A（BB → A），并跳过被合并的 B（++i）。 遇到 A 或 C 直接输出。单次扫描即可将字符串变为最优形式。

3. 边界与细节：

   • 当 i = N-1 时，s[i+1] 访问到字符串末尾的 \0，不会等于 'A' 或 'B'，因此不会触发任何操作，安全。
   • BB → A 时 ++i 会跳过下一个字符，配合 for 循环自身的 i++，实际一次跳过两个位置，保证输出长度正确。
   • 注意 C 的分隔作用：C 前后的 A/B 不能跨越 C 进行交换或合并。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，仅需一次从左到右的线性扫描。
• 空间复杂度：$O(N)$，存储输入字符串（可优化为 $O(1)$ 流式处理，但 std.cpp 使用 $O(N)$）。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int n;string s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='B')
		{
			// BA → AB：将 A 向左推，使字典序更小
			if(s[i+1]=='A')swap(s[i],s[i+1]);
			// BB → A：合并两个 B 为一个 A，并跳过下一个字符
			else if(s[i+1]=='B')s[++i]='A';
		}
		// 输出当前字符（A、C 或处理后的 B）
		cout<<s[i];
	}
	return 0;
}