首页 > 试题广场 >

小苯的魔法染色

[编程题]小苯的魔法染色
  • 热度指数：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 的最小可能值。

输入描述:
\hspace{15pt}输入包含两行。

\hspace{15pt}第一行输入两个正整数 n,m\ \left(1\leqq m\leqq n\leqq 2\times10^5\right)——墙的长度与小苯允许施法的最大次数。

\hspace{15pt}第二行输入一个长度为 n 的字符串 s，保证 s 仅由字符 \tt W 与 \tt R 组成。


输出描述:
\hspace{15pt}输出一个正整数，表示满足要求的最小 k。
示例1

输入

5 2
WRWWR

输出

2

说明

小苯可以进行 m = 2 次操作，每次操作的长度必须在 2 以内。
一种可能的染色方式是：选择 [1, 2] 再选择 [3,4]，操作后整面墙都会被染红，可以证明不存在单次操作比 2 更小的长度。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2025-03-20 16:42:38
题目描述 题目地址：24淘天春招-小苯的魔法染色 解题思路 这是一个最小化问题，我们需要找到能将整面墙染红的最小区间长度。关键思路如下： 使用二分查找来寻找最小的区间长度 对于每个猜测的长度 ，我们需要验证是否能在最多 次操作内将墙完全染红 验证过程中，我们采用贪心策略： 从左到右扫描墙面 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-11-14 14:54:18
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <string> using namespace std; b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 10:55:14
题目链接 小茶的魔法染色 题目描述 小红有一堵长度为 的墙，由 'W' (白色) 和 'R' (红色) 组成。她想将整面墙染成红色。 魔法师小茶可以施法，一次施法可以选择一个闭区间 并将其全部染红。他最多可以施法 次，且每次施法的区间长度 不得超过一个最大值 。 你需要找到能完成任务的最小的 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 二分 字符串
来自：2024年春招-淘天集...
难度：
13条回答 1820浏览

热门推荐

相关试题

小苯的魔法染色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号