题目描述

题目地址：24淘天春招-小苯的魔法染色 alt

解题思路

这是一个最小化问题，我们需要找到能将整面墙染红的最小区间长度。关键思路如下：

  1. 使用二分查找来寻找最小的区间长度
  2. 对于每个猜测的长度 ，我们需要验证是否能在最多 次操作内将墙完全染红
  3. 验证过程中，我们采用贪心策略：
    • 从左到右扫描墙面
    • 遇到白色格子时，尽可能覆盖最多的未染色区域

代码

#include <iostream>
#include <string>
using namespace std;

bool check(string& s, int m, int k) {
    int n = s.length();
    int count = 0;  // 操作次数
    int i = 0;
    while (i < n) {
        if (s[i] == 'W') {  // 遇到白色需要染色
            count++;
            if (count > m) return false;
            i = i + k;  // 跳过已染色的区域
        } else {
            i++;
        }
    }
    return true;
}

int solve(int n, int m, string& s) {
    int left = 0, right = n + 1;
    int ans = n;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(s, m, mid)) {
            ans = mid;
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    cout << solve(n, m, s) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static boolean check(String s, int m, int k) {
        int n = s.length();
        int count = 0;  // 操作次数
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == 'W') {  // 遇到白色需要染色
                count++;
                if (count > m) return false;
                i = i + k;  // 跳过已染色的区域
            } else {
                i++;
            }
        }
        return true;
    }
    
    public static int solve(int n, int m, String s) {
        int left = 0, right = n + 1;
        int ans = n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(s, m, mid)) {
                ans = mid;
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();
        System.out.println(solve(n, m, s));
        sc.close();
    }
}

def check(s, m, k):
    n = len(s)
    count = 0  # 操作次数
    i = 0
    while i < n:
        if s[i] == 'W':  # 遇到白色需要染色
            count += 1
            if count > m:  # 超过允许的操作次数
                return False
            i = i + k  # 跳过已染色的区域
        else:
            i += 1
    return True

def solve(n, m, s):
    left, right = 0, n + 1
    ans = n
    
    while left < right:
        mid = left + (right - left) // 2
        if check(s, m, mid):
            ans = mid
            right = mid
        else:
            left = mid + 1
            
    return ans

# 读取输入
n, m = map(int, input().split())
s = input()
print(solve(n, m, s))

算法及复杂度

  • 算法：二分查找 + 贪心
  • 时间复杂度：，其中 是墙的长度。二分查找的复杂度是，每次check函数需要的时间。
  • 空间复杂度：，只使用了常数额外空间。

同类题目推荐