算法1

单调队列优化好题

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 300010;
int sh[N], sg[N];
int s[N];
char cows[N];
int n, k;
int f[N];
int q[N], hh, tt;

bool less_than(int i, int j)
{
    if(f[i] != f[j]) return f[i] < f[j];
    return s[i] > s[j];
}

int main()
{
    scanf("%d%d", &n, &k);
    scanf("%s", cows + 1);
    for(int i = 1; i <= n; ++ i) sh[i] = sh[i - 1] + (cows[i] == 'H');
    for(int i = 1; i <= n; ++ i) sg[i] = sg[i - 1] + (cows[i] == 'G');
    for(int i = 1; i <= n; ++ i) s[i] = sg[i] - sh[i];
    hh = 0; tt = -1;
    q[++ tt] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        while(hh <= tt && q[hh] < i - k) hh ++;
        f[i] = f[q[hh]] + ((s[i] - s[q[hh]]) >= 0);
        while(hh <= tt && less_than(i, q[tt])) tt --;
        q[++ tt] = i;
    } 
    printf("%d", f[n]);
    return 0;
}