#include<iostream> #include<cstring> #include<queue> using namespace std; int n,k,pre[300001],dp[300001]; string s; struct hhh { int x,y; bool operator<(const hhh &t) const { if(xt.x) return pre[y]>pre[t.y]; else return x>t.x; } }p; priority_queue<hhh>q;//双关键字小根堆。 int main() { cin>>n>>k>>s; for(int i=n;i>=1;i--) s[i]=s[i-1]; //求前缀和。 for(int i=1;i<=n;i++) pre[i]=s[i]'H'?pre[i-1]+1:pre[i-1]-1; memset(dp,0x3f,sizeof(dp)); dp[0]=0; p.x=0; p.y=0; q.push(p); for(int i=1;i<=n;i++) { //如果最小值的位置过于靠前，就要把它弹掉。 while(q.top().y<i-k) q.pop(); dp[i]=pre[i]-pre[q.top().y]<=0?q.top().x+1:q.top().x; //将新出现的值压到堆中。 p.x=dp[i]; p.y=i; q.push(p); } cout<<dp[n]; return 0; }