Sweets for Everyone!（CF-248D）Problem DescriptionInputOutputExamplesNoteSource Program

80 阅读 0 评论 53 点赞

我是靠谱客的博主仁爱舞蹈，最近开发中收集的这篇文章主要介绍Sweets for Everyone!（CF-248D）Problem DescriptionInputOutputExamplesNoteSource Program，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

For he knew every Who down in Whoville beneath, Was busy now, hanging a mistletoe wreath. "And they're hanging their stockings!" he snarled with a sneer, "Tomorrow is Christmas! It's practically here!"
Dr. Suess, How The Grinch Stole Christmas
Christmas celebrations are coming to Whoville. Cindy Lou Who and her parents Lou Lou Who and Betty Lou Who decided to give sweets to all people in their street. They decided to give the residents of each house on the street, one kilogram of sweets. So they need as many kilos of sweets as there are homes on their street.

The street, where the Lou Who family lives can be represented as n consecutive sections of equal length. You can go from any section to a neighbouring one in one unit of time. Each of the sections is one of three types: an empty piece of land, a house or a shop. Cindy Lou and her family can buy sweets in a shop, but no more than one kilogram of sweets in one shop (the vendors care about the residents of Whoville not to overeat on sweets).

After the Lou Who family leave their home, they will be on the first section of the road. To get to this section of the road, they also require one unit of time. We can assume that Cindy and her mom and dad can carry an unlimited number of kilograms of sweets. Every time they are on a house section, they can give a kilogram of sweets to the inhabitants of the house, or they can simply move to another section. If the family have already given sweets to the residents of a house, they can't do it again. Similarly, if they are on the shop section, they can either buy a kilo of sweets in it or skip this shop. If they've bought a kilo of sweets in a shop, the seller of the shop remembered them and the won't sell them a single candy if they come again. The time to buy and give sweets can be neglected. The Lou Whos do not want the people of any house to remain without food.

The Lou Whos want to spend no more than t time units of time to give out sweets, as they really want to have enough time to prepare for the Christmas celebration. In order to have time to give all the sweets, they may have to initially bring additional k kilos of sweets.

Cindy Lou wants to know the minimum number of k kilos of sweets they need to take with them, to have time to give sweets to the residents of each house in their street.

Your task is to write a program that will determine the minimum possible value of k.

Input

The first line of the input contains two space-separated integers n and t (2 ≤ n ≤ 5·105, 1 ≤ t ≤ 109). The second line of the input contains n characters, the i-th of them equals "H" (if the i-th segment contains a house), "S" (if the i-th segment contains a shop) or "." (if the i-th segment doesn't contain a house or a shop).

It is guaranteed that there is at least one segment with a house.

Output

If there isn't a single value of k that makes it possible to give sweets to everybody in at most t units of time, print in a single line "-1" (without the quotes). Otherwise, print on a single line the minimum possible value of k.

Examples

Input

6 6
HSHSHS

Output

1

Input

14 100
...HHHSSS...SH

Output

0

Input

23 50
HHSS.......SSHHHHHHHHHH

Output

8

Note

In the first example, there are as many stores, as houses. If the family do not take a single kilo of sweets from home, in order to treat the inhabitants of the first house, they will need to make at least one step back, and they have absolutely no time for it. If they take one kilogram of sweets, they won't need to go back.

In the second example, the number of shops is equal to the number of houses and plenty of time. Available at all stores passing out candy in one direction and give them when passing in the opposite direction.

In the third example, the shops on the street are fewer than houses. The Lou Whos have to take the missing number of kilograms of sweets with them from home.

题意：有给出 n、t 两个整数，再给出一个长度为 n 的字符串，H 代表房子，S 代表商店，. 代表空地，现在从最左端行走，每走一步花费 1 分钟，可以向回走，但总时间不得超过 t，每遇到一个 H 要给出 1 单位的糖，每遇到一个 S 可以买 1 单位的糖，但每个商店只能买一次，现在要使得所有 H 都有 1 单位的糖，问在初始时携带的最少数量的糖，如果无法保证每个 H 都有 1 单位的糖，输出 -1

思路：

明显的二分答案，但难点在于二分的 judge 函数

假设初始时携带 k 单位的糖，到达某个 H 时糖果数量不够，那么有两种方案：

继续向前走，找到一个 S，获取一单位的糖再回去
遍历完所有的 H，并且糖果足够再回来

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N =5000000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
int n,t;
char str[N];
int numH;
int check(int mid,int step) {
int cnt=0;
int pos1=-1,pos2=0,sub=0;
for(int i=0; i<n; i++) {
if(cnt==numH&&mid>=0) {
if(step>=min(i-pos1,sub))
return true;
else
return false;
}
step--;
if(str[i]=='H') {
if(mid==0) {
if(pos1==-1)
pos1=i;
pos2=i;
}
mid--;
cnt++;
}
else if(str[i]=='S') {
mid++;
if(mid==0) {
sub+=i-pos2;
if(cnt!=numH)
sub+=i-pos2;
}
}
}
if(step>=min(n-1-pos1,sub)&&mid>=0)
return true;
else
return false;
}
int main() {
scanf("%d%d",&n,&t);
scanf("%s",str);
for(int i=0; i<n; i++) {
if(str[i]=='H')
numH++;
}
int left=0,right=numH;
while(left<right){
int mid=(left+right)>>1;
if(check(mid,t))
right=mid;
else
left=mid+1;
}
if(check(left,t))
printf("%dn",left);
else
printf("-1n");
return 0;
}