贪心题解

这道题是典型的贪心问题，关键要贪那一段含有O最多的地方，把它这个闭区间中的O都变成N

# include <iostream>
# include <algorithm>
using namespace std;
int main()
{
    int n, k, s = 0;
    cin >> n >> k;
    char clean[n + 1];
    cin >> clean;
    for (int i = 0; i < n / k + 1; i ++)
    {
        if (count(clean, clean + n, 'O') == 0) break;
        int largest_os = count(clean, clean + k, 'O'), index = 0, llos = largest_os;
        for (int j = 1; j < n - k + 1; j ++)
        {
            int os = llos - (clean[j - 1] == 'O') + (clean[j + k - 1] == 'O');
            if (os > largest_os) largest_os = os, index = j;
            llos = os;
        }
        for (int j = index; j < index + k; j ++)
            if (clean[j] == 'O')
                clean[j] = 'N';
        s++;
    }
    cout << s << endl;
    return 0;
}