题目描述
快乐字符串虽迟但到
给定一个长度为n的二进制字符串 s。
我们定义 di 为其十进制表示为 sisi+1 的数字(可能带有前导零)。我们定义 f(s) 为所有有效 di 的总和。换句话说,
f(s)=i=1∑n−1di.
例如,对于字符串 s=1011:
- d1=10;
- d2=01;
- d3=11;
- f(s)=10+01+11=22.
在一次操作中,你可以交换字符串中的任意两个相邻元素。如果允许最多 k 次操作,我们定义所有可达字符串中f(s)最小的那些为快乐字符串,请找到快乐字符串,并输出 f(s) 的最小值。
输入格式
本题含有多组测试数据。
第一行输入一个整数 T(1≤T≤105),表示测试数据组数。
接下来对于每组测试数据,第一行输入两个整数 n,k(2≤n≤105,0≤k≤109)——字符串的长度和允许的最大操作次数。
第二行输入一个长度为 n 的二进制字符串 s,仅由0和1组成。
题目保证:在单个测试文件中∑n≤105。
输出格式
对于每组测试数据,输出一行一个整数,你可以执行最多 k 次操作后 f(s) 的最小值。
样例
3
4 0
1010
7 1
0010100
5 2
00110
21
22
12
提示
对于第一组测试用例,你无法进行任何操作,因此快乐字符串就是 s本身。f(s)=f(1010)=10+01+10=21。
对于第二组测试用例,你可以获得的快乐字符串之一是"0011000",该字符串的f值为22。