灵茶之贪心模拟01

题目链接

https://codeforces.com/problemset/problem/1443/B

题目大意

输入 T(≤\(10^5\)) 表示 T 组数据。所有数据的字符串长度之和 ≤ \(10^5\)。

每组数据输入 a(1≤a≤1000) b(1≤b≤1000) 和长度不超过 \(10^5\) 的 01 字符串。

你可以花费 a，把一段连续的 1 变成 0。

也可以花费 b，把一个 0 变成 1。

上述两种操作可以执行任意次。 输出把所有 1 都变成 0 的最小花费。

题目思路

• 如果没有1，就直接输出0
• 考虑这样的一部分:1110001111
  • 我们有两种方案
  • ①将两边连续的1花费a变成0，总花费为2a
  • ②将中间0花费 k * b 变成1,在花费a将1变成0，总花费为 kb + a
  • 比较方案①与方案②，自然是选择总花费最小的方案了
• 我们只需从左往右使用双指针[left,right]，找到两段 1中间的那串0，考虑将这两段1合并成一段1的最小花费，再加上最后合并成的那一连串1的花费a即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,a,b,t;
void solve() {
    string s;
    cin >> a >> b;cin >> s;
    n = (int)s.size();
    // s 里 不 包 含 0！
    if(s.find('1') == string::npos) {
        cout << 0 << '\n';
        return;
    }
    int ans = a;
    int right = 0,left;
    while(right < n){
        char x = s[right];
        left = right;
        while(right < n && s[right] == x) ++right;
        if(x == '0' && right < n){
            if(left == 0) continue;
            ans += min(b * (right - left),a);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    for (int _ = 0; _ < t; _++) solve();
    return 0;
}