题目描述

难度分:$1300$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的字符串长度之和$\leq 10^5$。
每组数据输入$a(1 \leq a \leq 1000)$，$b(1 \leq b \leq 1000)$和长度不超过$10^5$的$01$字符串。

• 你可以花费$a$，把一段连续的$1$变成$0$。
• 也可以花费$b$，把一个$0$变成$1$。

上述两种操作可以执行任意次。

输出把所有$1$都变成$0$的最小花费。

输入样例

2
1 1
01000010
5 1
01101110

输出样例

2
6

算法

反悔贪心

遍历一遍$s$串，可以得到一个初始花费（直接将每一段连续的$1$变成$0$，答案应该是连续$1$段的个数乘以$A$）。然后再遍历一遍$s$串中最长的以$1$开头和结尾的子串$[l,r]$（两端的$0$不需要考虑），将其中连续的$0$段长度放入到一个大根堆中。

通过分析我们可以发现，把一段连续的$0$翻转使得两个连续的$1$段能够连接起来，这个将$0$翻转成$1$的操作才是有效的。而每连接起两个连续的$1$段，意味着花费为$A$的操作就会少一次，因此可以初始化一个代价$cost$，就是将子串$[l,r]$中的所有$0$翻转为$1$，然后将子串$[l,r]$全部翻转成$0$。接下来每次从大根堆中弹出一个最长的$0$段，表示这一段长度为$len$的连续$0$不翻转，这时候会多增加一个代价为$A$的操作，$cost=cost-len \times B+A$，每次都弹出堆顶元素，维护$cost$的最小值。

复杂度分析

时间复杂度

遍历$s$串时存在往堆中插入元素的操作，插入的时间复杂度为$O(log_2n)$，因此整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于大根堆，最差情况下会放入$O(n)$级别的元素数量，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int N = 100010;
char s[N];
int a, b, n, T;

void solve() {
    int ans = 0, one = 0;
    // 所有连续段的1直接翻转
    int l = 0, r = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '1') {
            one++;
            if(l == 0) l = i;
            r = i;
        }else {
            if(one > 0) {
                ans += a;
                one = 0;
            }
        }
    }
    if(one > 0) {
        ans += a;
        one = 0;
    }
    // 反悔贪心
    int cnt0 = 0;
    int zero = 0;
    priority_queue<int> heap;
    for(int i = l; i <= r; i++) {
        if(s[i] == '0') {
            zero++;
            cnt0++;
        }else {
            if(zero > 0) {
                heap.push(zero);
                zero = 0;
            }
        }
    }
    ans = min(ans, cnt0*b + a);
    int cnt1 = 1;
    while(heap.size()) {
        cnt0 -= heap.top();
        heap.pop();
        cnt1++;
        ans = min(ans, cnt0*b + cnt1*a);
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &a, &b);
        scanf("%s", s + 1);
        n = strlen(s + 1);
        solve();
    }
    return 0;
}