题目描述

难度分:$1800$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq 10^9)$和长为$n$的01字符串$s$。

有$n$条鱼排成一排，其中$s[i]=$0表示第$i$条鱼是$Alice$的，$s[i]=$1表示第$i$条鱼是$Bob$的。

你需要把$s$分割成若干个非空段。第一段所有鱼的价值是$0$，第二段所有鱼的价值是$1$，第三段所有鱼的价值是$2$，依此类推。

最少分成多少段，可以让$Bob$的鱼的价值之和$-Alice$ 的鱼的价值之和$\geq k$？如果无法做到，输出$-1$。

输入样例

7
4 1
1001
4 1
1010
4 1
0110
4 2
0110
6 3
001110
10 20
1111111111
5 11
11111

输出样例

2
-1
2
-1
3
4
-1

算法

贪心

这个题的关键在于分析清楚性质，性质找到了就可以排个序贪心了。假设有这么一个例子，初始有$4$段

100|110|10|11

此时$Bob$的得分减去$Alice$的得分为$0 \times 1 - 0 \times 2+1 \times 2-1 \times 1+2 \times 1-2 \times 1+3 \times 2-3 \times 0=7$

如果在第$2$段中间划一刀变成

100|1|10|10|11

其实前两段是没有变化的，主要的增量是$3$~$5$段带来的，每个段的价值因为新增一段的缘故，全部都增加了$1$。所以这个分割点$4$（在$4$索引的后面分割）的增量为$\Sigma_{i \in [5,10]}s[i]-(6-\Sigma_{i \in [5,10]}s[i])$，再试几个分割点就可以发现，$i$能够给“$Bob$的鱼的价值之和$-Alice$ 的鱼的价值之和”带来的增量就是$(i,n]$上$1$的数量减去$0$的数量。

预处理出两个后缀和数组$one$和$zero$，$one[i]$和$zero[i]$分别表示后缀$[i,n]$上$1$和$0$的数量。将所有分割点的增量存入$vals$数组（因为$i=0$不能为分割点，否则第一段就是空了，不合题意，所以$vals$中不会有$one[1]-zero[1]$）。

最后对$vals$排序，从大到小遍历，只要累加和$\geq k$就停止遍历，打印段数。

复杂度分析

时间复杂度

预处理出$one$和$zero$两个前缀和数组时间复杂度为$O(n)$；将每个分割点的收益$vals$排序时间复杂度为$O(nlog_2n)$；最后求答案需要遍历分割点，时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

主要空间消耗在于$zero$、$one$、$vals$，都是线性空间，所以额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n, k, one[N], zero[N];
char s[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        scanf("%s", s + 1);
        one[n + 1] = zero[n + 1] = 0;
        for(int i = n; i >= 1; i--) {
            one[i] = one[i + 1] + (s[i] == '1'? 1: 0);
            zero[i] = zero[i + 1] + (s[i] == '0'? 1: 0);
        }
        vector<int> vals;
        for(int i = 2; i <= n; i++) {
            vals.push_back(one[i] - zero[i]);
        }
        sort(vals.begin(), vals.end());
        reverse(vals.begin(), vals.end());
        int cnt = 1;    // 初始有一段
        long long s = 0;
        for(int val: vals) {
            s += val;
            cnt++;
            if(s >= k) {
                break;
            }
        }
        printf("%d\n", s >= k? cnt: -1);
    }
    return 0;
}