一、问题重述与模型转化

原题描述

我们有 $n$ 只排成一排的泰迪熊，颜色为黑色（B）和粉色（P）。 美观排列：所有黑色熊在左侧，所有粉色熊在右侧。 操作规则：每次选择连续 3 个位置，将这 3 只熊重新排序为黑左粉右。 求将原排列变为美观排列的最少操作次数。

核心模型转化

为了方便计算，我们做等价替换：

• 黑色泰迪熊 $\boldsymbol{B} \rightarrow 0$
• 粉色泰迪熊 $\boldsymbol{P} \rightarrow 1$

此时问题转化为： 给定一个 01 数组，每次操作可以选择连续三个元素并将其升序排序，求将整个数组升序排序所需的最小操作次数。

---

二、操作类型与逆序数分析

1. 所有可能的三元组操作

每次操作仅对连续三个元素生效，排序后结果固定，共 4 种有效变化：

1. 操作 A：$(0,1,0) \rightarrow (0,0,1)$
2. 操作 B：$(1,0,0) \rightarrow (0,0,1)$
3. 操作 C：$(1,0,1) \rightarrow (0,1,1)$
4. 操作 D：$(1,1,0) \rightarrow (0,1,1)$

2. 逆序数（关键指标）

逆序对：在数组中，满足 $i<j$ 且 $a[i]>a[j]$ 的数对。 整个数组的逆序对总数记为 $\boldsymbol{x}$。 排序完成后，逆序数一定为 0，因此操作的核心目标是减少逆序数。

3. 各操作对逆序数的影响

• 操作 A：逆序数 $-1$
• 操作 B：逆序数 $-2$
• 操作 C：逆序数 $-1$
• 操作 D：逆序数 $-2$

4. 贪心策略

优先使用每次减少 2 个逆序对的操作 B、D，效率最高。 仅在无法使用 B、D 时，才使用减少 1 个逆序对的操作 A、C。

---

三、奇偶性约束（核心难点）

1. 仅用 B/D 操作后的数组形态

如果我们只执行最优操作 B、D，最终数组会变成： [0...0, 1,0,1,0..., 1...1] 即：前缀全 0 + 中间交替 1/0 + 后缀全 1。 此时无法再用 B/D 操作，剩余逆序对无法通过高效操作消除。

2. 定义关键变量

• $\boldsymbol{a}$：数组中 0（黑色熊）的总数量
• $\boldsymbol{b}$：数组中，偶数下标位置上 0（黑色熊）的数量 （下标从 1 开始计数）

3. 最终状态的奇偶性要求

排序完成后，所有 0 集中在数组最左侧：

• 偶数位置上的 0 数量固定为：$\boldsymbol{\lfloor \frac{a}{2} \rfloor}$

4. 操作对奇偶性的影响

• 操作 B、D：不改变 $b$ 的值
• 操作 A、C：可以改变 $b$ 的值（±1）

这意味着：必须用 A/C 操作修正奇偶性偏差。

---

四、公式推导

1. 计算奇偶性偏差

$$d = \left| \left\lfloor \frac{a}{2} \right\rfloor - b \right| $$

$d$ 是我们必须使用**低效操作（A/C）**的次数，每次只能减少 1 个逆序对。

2. 总操作数公式

• 总逆序数：$x$
• 低效操作消耗逆序数：$d$
• 剩余逆序数：$x-d$（必为偶数）
• 高效操作次数：$\frac{x-d}{2}$

最终总操作数：

$$\boldsymbol{ans = \frac{x + d}{2}}$$

---

五、代码实现详解

1. 变量定义

• x：总逆序对数量
• a：黑色熊（B）的总数
• b：偶数下标位置上黑色熊（B）的数量

2. 逆序对计算技巧

从右向左遍历数组：

• 遇到 B：统计数量，判断是否在偶数位置
• 遇到 P：累加右侧已统计的 B 数量（即新增逆序对）

3. 完整代码

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    long long x = 0;
    int a = 0;
    int b = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'B') {
            a++;
            if ((i + 1) % 2 == 0) {
                b++;
            }
        }
        if (s[i] == 'P') {
            x += a;
        }
    }

    int d = abs(a / 2 - b);
    cout << (x + d) / 2 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}