题目解析

问题重述

有 $n$ 条鱼按编号从小到大排列（编号越大表示鱼越大）。每条鱼被 Alice（字符 0）或 Bob（字符 1）钓到。我们需要将鱼分成 $m$ 个非空连续组，第 $i$ 组的每条鱼获得价值 $i-1$。设 Bob 的总价值为 $B$，Alice 的总价值为 $A$。要求 $B - A \ge k$，求最小的 $m$。如果不可能，输出 $-1$。

核心思想

1. 从“组边界”的角度思考

每组鱼的价值等于它前面有多少组。换句话说，每增加一个组边界，该边界之后的所有鱼的价值都会 +1。

设第 $j$ 个组边界位于第 $i$ 条鱼之后（即第 $1 \sim i$ 条鱼是前 $j$ 组，第 $i+1 \sim n$ 条鱼是后面的组）。那么这个边界会让第 $i+1$ 条及之后的所有鱼的价值都增加 $1$。

2. 得分差的贡献

对于第 $i$ 条鱼和第 $i+1$ 条鱼之间的位置，如果这里有一个组边界，那么它会给 Bob 和 Alice 的得分差贡献：

设 $s_i$ 表示从第 $i$ 条鱼到第 $n$ 条鱼中，Bob 的鱼数减去 Alice 的鱼数。更精确地：

$$s_i = \sum_{j=i}^{n} \begin{cases} +1 & \text{if fish } j \text{ is Bob's} \\ -1 & \text{if fish } j \text{ is Alice's} \end{cases} $$

那么，在第 $i$ 条鱼之后放置一个组边界（即第 $i$ 条鱼和第 $i+1$ 条鱼在不同组），会对最终得分差贡献 $s_{i+1}$。

3. 得分差的最终表达式

设第 $1$ 组从第 $1$ 条鱼开始，第 $2$ 组从第 $p_2$ 条鱼开始，…，第 $m$ 组从第 $p_m$ 条鱼开始，其中 $1 = p_1 < p_2 < \dots < p_m \le n$。那么 Bob 与 Alice 的得分差为：

$$B - A = \sum_{j=1}^{m} (j-1) \cdot (\text{第 } j \text{ 组中 Bob 鱼数} - \text{Alice 鱼数}) $$

展开后可得：

$$B - A = 0 \cdot s_{p_1} + 1 \cdot s_{p_2} + 2 \cdot s_{p_3} + \dots + (m-1) \cdot s_{p_m} $$

其中 $s_{p_j}$ 表示从第 $p_j$ 条鱼开始的差值累积和。这个表达式可以重写为：

$$B - A = s_{p_2} + s_{p_3} + \dots + s_{p_m}$$

为什么？因为第 $j$ 组边界的贡献是 $s_{p_{j+1}}$，而最后一组之后没有边界。实际上：

• 第 $1$ 组中的鱼价值为 $0$，贡献 $0$
• 第 $2$ 组中的鱼比第 $1$ 组多 $1$ 分，这个 $1$ 分来自第 $1$ 个组边界，贡献 $s_{p_2}$
• 第 $3$ 组中的鱼比第 $2$ 组多 $1$ 分，这部分贡献 $s_{p_3}$，等等。

所以最终：

$$B - A = \sum_{j=2}^{m} s_{p_j}$$

4. 转化为选择问题

因此，$B - A$ 等于若干个 $s_i$ 值的和，其中 $i$ 是每个组边界的位置（除了第一个组没有前边界）。$s_i$ 是从位置 $i$ 到末尾的净差值。

由于 $s_i$ 可以为负数，而我们的目标是让 $B-A \ge k$，我们只关心正数的 $s_i$（因为加入负数只会减小总和，对达到目标没有帮助）。

5. 最小化组数

组数 $m$ 等于“选择的 $s_i$ 的数量” $+ 1$（因为第一个组没有前边界）。为了用最少的组数达到目标，我们应该选择最大的 $s_i$ 值。

6. 算法步骤

1. 从右向左遍历，计算后缀差值 $s_i$（Bob 为 $+1$，Alice 为 $-1$）
2. 收集所有 $s_i > 0$ 的值（$i$ 从 $1$ 到 $n-1$，因为最后一个位置之后不需要边界）
3. 将收集的值从大到小排序
4. 依次取最大的值累加，直到总和 $\ge k$
5. 答案 = 取的数量 $+ 1$（如果累加和 $\ge k$），否则输出 $-1$

示例验证

示例 1: $n=4, k=1, s=\text{"1001"}$

• 从右向左计算 $s_i$：
  • $s_4$（鱼4: Bob）$= +1$
  • $s_3$（鱼3: Alice）$= -1 + 1 = 0$
  • $s_2$（鱼2: Alice）$= -1 + 0 = -1$
  • $s_1$（鱼1: Bob）$= +1 + (-1) = 0$
• $s_i > 0$ 的值：$[1]$
• 取 $1 \ge 1$，取了 $1$ 个值
• $ans = 1 + 1 = 2$ ✅

示例 3: $n=4, k=1, s=\text{"0110"}$

• 从右向左：$s_4=0, s_3=+1, s_2=+1+1=2, s_1= -1+2=1$
• $s_i > 0$：$[1,2,1]$（位置 $1,2,3$）
• 排序：$[2,1,1]$
• 取 $2 \ge 1$，取了 $1$ 个值
• $ans = 2$ ✅

示例 5: $n=6, k=3, s=\text{"001110"}$

• 计算 $s_i$（$i$ 从 $6$ 到 $1$）：
  • 鱼6: 0 → $-1$
  • 鱼5: 1 → $+1$, $s_5 = -1+1=0$
  • 鱼4: 1 → $+1$, $s_4 = 0+1=1$
  • 鱼3: 1 → $+1$, $s_3 = 1+1=2$
  • 鱼2: 0 → $-1$, $s_2 = 2-1=1$
  • 鱼1: 0 → $-1$, $s_1 = 1-1=0$
• $s_i > 0$：$[1,2,1]$
• 排序：$[2,1,1]$
• 取 $2 < 3$，再取 $2+1=3 \ge 3$，取了 $2$ 个值
• $ans = 2 + 1 = 3$ ✅

C++ 代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        
        vector<int> vals;
        int sum = 0;
        
        // 从右向左计算后缀差值
        for (int i = n - 1; i > 0; --i) {
            sum += (s[i] == '1' ? 1 : -1);
            if (sum > 0) {
                vals.push_back(sum);
            }
        }
        
        // 从大到小排序
        sort(vals.begin(), vals.end(), greater<int>());
        
        int ans = 1;  // 至少有一组
        for (int x : vals) {
            if (k <= 0) break;
            k -= x;
            ++ans;
        }
        
        cout << (k > 0 ? -1 : ans) << '\n';
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自排序
• 空间复杂度：$O(n)$
• 所有测试用例 $n$ 总和 $\le 2 \times 10^5$，完全可行

关键点总结

1. 组边界贡献模型：每个组边界给后面所有鱼的价值 +1
2. 后缀差值数组：$s_i$ 表示从位置 $i$ 开始的净差值
3. 得分差 = 所选 $s_i$ 之和（$i$ 为组边界位置）
4. 贪心选择：取最大的 $s_i$ 以最小化组数
5. 答案 = 选取数量 + 1（第一个组不需要前边界）