问题重述

有 $2N$ 只河狸排成一排，$N$ 只唱 A 声部，$N$ 只唱 B 声部。要将它们分成 $K$ 组（歌曲），每组需满足：

1. 至少一只河狸
2. A 声部数量 = B 声部数量
3. 组内所有 A 声部河狸都在所有 B 声部河狸的右边

只能通过交换相邻河狸来调整位置，求最少交换次数。

---

关键观察

1. 条件分析

第三个条件「所有A都在所有B的右边」意味着：对于任意一组，其成员的排列形如：

[一些B] [一些A]

且 A 的数量 = B 的数量。

2. 问题转化

设最终分组为 $K$ 段，每段包含 $2t_i$ 只河狸（$t_i$ 对 A-B）。

由于 A 的总数 = B 的总数 = $N$，我们有：

$$\sum_{i=1}^K t_i = N$$

3. 位置约束

考虑最终排列中 A 和 B 的分布：

• 第 $i$ 组需要 $t_i$ 个 A 和 $t_i$ 个 B
• 所有组的 A 必须按组顺序排在对应组的 B 的右边

这实际上要求最终的排列形如：

[B...B A...A] [B...B A...A] ... [B...B A...A]

其中第 $i$ 个块有 $t_i$ 个 B 和 $t_i$ 个 A。

---

核心解法

1. 最优结构

关键结论：存在最优解，使得最终排列是：

• 前 $t_1$ 个位置是第1组的 B
• 接着 $t_1$ 个位置是第1组的 A
• 接着 $t_2$ 个位置是第2组的 B
• 接着 $t_2$ 个位置是第2组的 A
• ...
• 最后 $t_K$ 个位置是第K组的 A

2. 代价计算

设原序列中：

• $posA[i]$ = 第 $i$ 个 A 的原始位置（从左到右编号 1..2N）
• $posB[i]$ = 第 $i$ 个 B 的原始位置

在最终排列中：

• 第 $j$ 组的 B 占据位置：$2\sum_{i=1}^{j-1} t_i + 1$ 到 $2\sum_{i=1}^{j-1} t_i + t_j$
• 第 $j$ 组的 A 占据位置：$2\sum_{i=1}^{j-1} t_i + t_j + 1$ 到 $2\sum_{i=1}^{j} t_i$

交换次数 = 将每个河狸移动到目标位置的距离和。

3. 问题简化为划分问题

我们需要将 $N$ 个 A 和 $N$ 个 B 分成 $K$ 组，每组 $t_i$ 对，最小化总移动距离。

设：

• $preA[i]$ = 前 $i$ 个 A 的原始位置和
• $preB[i]$ = 前 $i$ 个 B 的原始位置和

对于给定的划分 $0 = p_0 < p_1 < \cdots < p_K = N$，其中 $p_j = \sum_{i=1}^j t_i$，代价为：

$$\sum_{j=1}^K \left[ \sum_{k=p_{j-1}+1}^{p_j} (2p_{j-1} + k - posB[k]) + \sum_{k=p_{j-1}+1}^{p_j} (2p_{j-1} + t_j + k - posA[k]) \right] $$

化简后是关于 $p_j$ 的二次函数，可以使用动态规划优化。

---

算法框架

1. 预处理

1. 提取所有 A 和 B 的位置
2. 计算前缀和 $preA[i]$, $preB[i]$

2. 动态规划

设 $dp[i][j]$ = 将前 $i$ 对 A-B 分成 $j$ 组的最小代价。

转移：

$$dp[i][j] = \min_{0 \le k < i} \{ dp[k][j-1] + cost(k+1, i) \} $$

其中 $cost(l, r)$ 是将第 $l$ 到第 $r$ 对 A-B 作为一组的代价。

3. 代价函数

经过推导，$cost(l, r)$ 可以写成：

$$cost(l, r) = C + \alpha \cdot l + \beta \cdot r + \gamma \cdot l^2 + \delta \cdot r^2 + \epsilon \cdot lr $$

的具体形式，满足决策单调性。

4. 优化

由于代价函数满足四边形不等式，可以使用分治优化将复杂度从 $O(KN^2)$ 降到 $O(KN \log N)$。

对于 $N \le 10^6$ 需要进一步观察性质：

关键性质：最优解中 $t_i$ 的差异不超过 1，即 $t_i \in \{\lfloor N/K \rfloor, \lceil N/K \rceil\}$。

---

最终算法

1. 确定分组大小：$a = \lfloor N/K \rfloor$, $b = \lceil N/K \rceil$

   • 有 $K_1$ 组大小为 $a$，$K_2$ 组大小为 $b$，满足 $K_1 + K_2 = K$, $K_1a + K_2b = N$

2. 计算最小代价：

   • 枚举 $K_1$ 和 $K_2$ 的排列方式
   • 对于每种排列，直接计算总移动距离

3. 输出最小代价

---

复杂度分析

• 确定分组：$O(1)$
• 计算代价：$O(N)$
• 总复杂度：$O(N)$，适合 $N \le 10^6$

---

总结

这道题的核心在于：

1. 理解分组条件：A 必须在 B 的右边，且数量相等
2. 发现最优结构：排列形如 [B...B A...A] 的连续块
3. 代价计算：将问题转化为划分问题
4. 优化决策：利用分组大小的均匀性降低复杂度

通过分析问题的组合结构，我们将看似复杂的交换问题转化为简洁的数学优化问题。