题目描述
难度分:1800
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(2≤n≤2×105),k(1≤k≤109)和长为n的01
字符串s。
有n条鱼排成一排,其中s[i]=0
表示第i条鱼是Alice的,s[i]=1
表示第i条鱼是Bob的。
你需要把s分割成若干个非空段。第一段所有鱼的价值是0,第二段所有鱼的价值是1,第三段所有鱼的价值是2,依此类推。
最少分成多少段,可以让Bob的鱼的价值之和−Alice 的鱼的价值之和≥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×1−0×2+1×2−1×1+2×1−2×1+3×2−3×0=7
如果在第2段中间划一刀变成
100|1|10|10|11
其实前两段是没有变化的,主要的增量是3~5段带来的,每个段的价值因为新增一段的缘故,全部都增加了1。所以这个分割点4(在4索引的后面分割)的增量为Σi∈[5,10]s[i]−(6−Σi∈[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排序,从大到小遍历,只要累加和≥k就停止遍历,打印段数。
复杂度分析
时间复杂度
预处理出one和zero两个前缀和数组时间复杂度为O(n);将每个分割点的收益vals排序时间复杂度为O(nlog2n);最后求答案需要遍历分割点,时间复杂度为O(n)。因此,整个算法的时间复杂度为O(nlog2n)。
空间复杂度
主要空间消耗在于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;
}