Feeding the Cows (USACO Bronze 2022 December)

$N=10^5$ 头G牛或H牛站成一排，每头牛需要 $K$ 距离内有一块对应的G草或H草，输出最节省的种草方案。

潜在总方案数很大（ $2^{10^5}$ ），所以我们看看是否有贪心这样的快速的策略。如果我们从左往右扫描的话，对于一头没有草地覆盖的牛，位置在 $i$ ，我们可以选择往右最远的地方，也就是 $i+K$ 种草，这样可以覆盖最多的后续的牛。思考一下可以发现，这个策略应该是最优的。一般情况下，这个位置肯定是空的，因为我们是从左往右扫描的。

唯一剩下的问题，是到最后的时候，最远的地方可能已经超出了边界，这时需要处理一下。简单地想，我们可以从右往左回过来扫描找一个空的位置，这时要问，是否一定存在一个能覆盖当前牛，但又是空的位置？答案是肯定的，试一些 $K$ 的值和不同的情况，可以直观地看出来的确是这样的，比赛现场就可以直接写的。如果需要证明，可以这样：

首先这时K肯定大于0，因为K=0的时候，每头牛脚下都种一块草，没有超出边界这个问题。所以 $K>0$ ，此时当 $i+K>N$ 时，我们可以证明最后两块地方（ $N-1$ 和 $N$ ）一定至少有一块是空的，因为如果这两块都是满的，一定一个是G草，一个是H草（同样草相邻显然是浪费的），必然已经覆盖了当前的牛，与当前牛没有草地覆盖相矛盾。所以 $N$ 和 $N-1$ 中至少有一个空地，种上草就可以。

所以我们找到了一个最优的贪心策略。

从左往右扫描，碰到未被覆盖的牛，位置 $i$ ，则在 $i+K$ 处种对应的草，并记录这个位置。
如果 $i+K>N$ ，则从在 $N$ , $N-1$ 中至少有一个空地，种上草就可以。

复杂度是 $\mathcal{O}(N)$ 。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
 
int T,n,k;
char s[100005];
char g[100005];
 
// place ideally at x. if x is out of bounds, then find a place
// return actual place
int place(int x, char c) {
    if (x < n) {
        g[x] = c;
        return x;
    }
    for (int i = n-1; i >= 0; i--)
        if (g[i] == '.') {
            g[i] = c;
            return i;
        }
    return -1;
}
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &n, &k);
        scanf("%s", s);
        memset(g, '.', n+1);
 
        int gend = 0, hend = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'G' && i >= gend) {                
                gend = place(i+k, 'G') + k + 1;
                cnt++;
            }
            if (s[i] == 'H' && i >= hend) {
                hend = place(i+k, 'H') + k + 1;
                cnt++;
            }
        }
        printf("%d\n", cnt);
        for (int i = 0; i < n; i++)
            printf("%c", g[i]);
        printf("\n");
    }
 
    return 0;
}