首页 > 试题广场 >

小苯的魔法染色

[编程题]小苯的魔法染色

热度指数：1087 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红面前有一堵长度为 $n$ 的墙，用一个只由 $\tt W$ （白色）和 $\tt R$ （红色）组成的字符串 $a_1a_2\dots a_n$ 表示。她希望最终将整面墙全部染成红色。

$\hspace{15pt}$ 为此她请来了魔法师小苯。一次施法的流程如下：
$\hspace{23pt}\bullet\,$ 小苯选择一个闭区间 $[l,r]\ (1\leqq l\leqq r\leqq n)$ ；
$\hspace{23pt}\bullet\,$ 立刻将区间内的所有格子染成红色。

$\hspace{15pt}$ 小苯至多施法 $m$ 次，且每次施法的区间长度 $\left(r-l+1\right)$ 不得超过 $k$ 。

$\hspace{15pt}$ 现在小苯想知道，将整堵墙染成红色所需的最小 $k$ 是多少。请你求出这个 $k$ 的最小可能值。

输入描述:

输入包含两行。

第一行输入两个正整数 ——墙的长度与小苯允许施法的最大次数。

第二行输入一个长度为  的字符串 ，保证  仅由字符  与  组成。

输出描述:

输出一个正整数，表示满足要求的最小 。

示例1

输入

5 2
WRWWR

输出

说明

小苯可以进行  次操作，每次操作的长度必须在  以内。
一种可能的染色方式是：选择  再选择 ，操作后整面墙都会被染红，可以证明不存在单次操作比  更小的长度。

算法知识视频讲解

查看答案及解析

推荐

小小

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define inf 1e18
typedef long long ll;
#define int long long


int n, m;
string s;

bool check(int mid) {
    vector<int> dp(n + 1, 1e18);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'R') {
            dp[i] = dp[i - 1];
        }
        else {
            dp[i] = dp[max(0LL, i - mid)] + 1;
        }
    }
    return dp[n] <= m;
}

void solve() {
    cin >> n >> m >> s;
    s = " " + s;
    int l = 0, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}


/*	

5 2
WRWWR
2

3 1
RRR

3 3
WWW

*/

signed main () {
//     init(minp, primes, m); // primes
    // init();
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
//   cin >> _;
    while(_ -- ) {
        solve();
    }
    return 0;
}

编辑于 2025-02-18 17:23:21 回复(0)

Python

Fansv587

n, m = map(int, input().split())
wall = input()



def can_paint(k):
    count = 0
    i = 0
    while i < n:
        # 找到当前位置右侧最近的白色格子
        j = i
        while j <  n and wall[j] == 'R':
            j += 1
        if j == n:
            break
        end = min(j + k - 1, n - 1)
        i = end + 1
        count += 1
    return count <= m

# 因为最少要涂一块，所以left = 1
left, right = 1, n
while left < right:
    mid = (left + right) // 2
    if can_paint(mid):
        right = mid
    else:
        left = mid + 1

# 检查一下是不是真的不需要涂
wuhu = [char for char in wall if char == 'W']
if wuhu == []:
    print(0)
else:
    print(left)

发表于 2025-03-05 15:06:37 回复(0)

提交观点

问题信息

贪心二分字符串

来自：2024年春招-淘天集...

难度：

1条回答 37收藏 1821浏览

小苯的魔法染色

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题