CF248D Sweets for Everyone!

因为他知道在 Whoville 村庄下面的每一个 Who 都正忙着挂槲寄生花环。“他们正在挂他们的圣诞袜！”他一边咆哮一边冷笑，“明天就是圣诞节！几乎就要到了！” ——Dr. Suess，《How The Grinch Stole Christmas》 圣诞节即将来到 Whoville。Cindy Lou Who 和她的父母 Lou Lou Who 以及 Betty Lou Who 决定给他们街道上的所有人送糖果。他们决定给街道上每一户居民送一公斤糖果。所以他们需要的糖果重量等于街道上的房屋数量。 Lou Who 一家的街道可以被表示为 $n$ 个连续、长度相等的路段。你可以在 1 单位时间内从当前路段走到相邻的另一个路段。每个路段有三种类型：空地、房屋或商店。Cindy Lou 和她的家人可以在商店买糖果，但每家店最多只能买 1 公斤糖果（卖家担心 Whoville 的居民吃太多糖果）。 Lou Who 一家离开家后，他们将处于道路的第一个路段。为了到达这个路段，也需要 1 单位时间。我们可以假设 Cindy 全家可以携带无限的糖果。每次他们在房屋路段上时，他们可以给该房屋的居民送 1 公斤糖果，或者直接移动到下一个路段。如果已经给某户居民送过糖果，则不能再次送给这家。同理，如果他们在商店路段上，可以在这里买 1 公斤糖果，或者跳过该商店。如果他们已经在商店买过糖果，店主会记得，不会再卖给他们。买糖果和送糖果的时间可以忽略。Lou Who 一家不希望有任何一家居民拿不到糖果。 Lou Who 一家希望在不超过 $t$ 单位时间内把所有糖果送完，因为他们还要留出时间准备圣诞庆祝活动。为了能及时送完他们也许需要一开始就带上额外 $k$ 公斤糖果。 Cindy Lou 想知道他们最少需要带多少 $k$ 公斤糖果，才能保证能在 $t$ 单位时间内把糖果送到街道上每一户人家。 你的任务是写一个程序，计算 $k$ 的最小可能值。

第一行包含两个用空格分隔的整数 $n$ 和 $t$（$2 \leq n \leq 5 \cdot 10^{5},\, 1 \leq t \leq 10^{9}$）。第二行包含 $n$ 个字符，第 $i$ 个字符为 “H”（如果第 $i$ 段是房屋）、“S”（如果第 $i$ 段是商店）或 “.”（如果第 $i$ 段既不是房屋也不是商店）。 保证至少存在一个房屋路段。

如果不存在任何 $k$ 使得能够在不超过 $t$ 单位时间内将糖果送给所有居民，输出一行 “-1”。否则，输出一行最小的 $k$。

在第一个样例中，商店数量与房屋数量相同。如果家里一公斤糖果都不带，为了给第一个房屋居民送糖果，他们需要至少后退一步，但他们完全没有时间。如果他们带上一公斤糖果，就无需回头。 在第二个样例中，商店数量等于房屋数量且时间充足。他们可以在所有经过的商店买糖果送出，然后原路返回时分发糖果。 在第三个样例中，街道上的商店数量少于房屋数量。Lou Who 一家必须随身携带缺少的糖果。 由 ChatGPT 5 翻译