← 返回比赛

已结束 2024新春欢乐赛

← 上一题下一题 →

A1758 | $新年大扫除$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

新年到了 *小k* 决定进行大扫除。 现在给你 $n$ 个字符表示大扫除当前状态，由大写字母 $N$ 和 $O$ 组成。$N$ 代表已经打扫过的地方，$O$ 表示没有打扫过的地方。 你现在可以任意选取 $k$ 个连续的位置进行打扫，将 $O$ 变成 $N$。可以进行多次！ 你最少几次就能把所有位置打扫完成呢？

输入格式

第一行包含两个整数 $n$ 和 $k$，其中 $1 \leq k \leq n \leq 10 ^ 6$。 第二行输入 $n$ 个位置的状态，由大写字母 $N$ 和$O$ 组成。

输出格式

在一行中输出打扫完所有位置需要的最小操作数。

输入输出样例

输入 #1

8 2
ONONOOOO

输出 #1

输入 #2

5 5
OOOOO

输出 #2

C++ 编辑器

输入

输出