Feeding the Cows

题意

有 N 头牛排成一行，每头牛是 G 或 H。

可以在某些位置种草，G 草只能喂 G 牛，H 草只能喂 H 牛。每头牛最多走 K 个位置去吃同品种草。

求最少种多少块草，并输出任意一种最优方案。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:15
 * update_at: 2026-07-11 17:16
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int INF = 1e9;

int n, k;
char cow[MAXN];
char choose_plan[MAXN]; // 每个位置选择 '.', 'G', 'H'
char best_plan[MAXN];
int best_count;

bool current_plan_valid() {
    for (int i = 1; i <= n; i++) {
        bool ok = false;
        for (int j = 1; j <= n; j++) {
            if (choose_plan[j] == cow[i] && abs(i - j) <= k) {
                ok = true;
                break;
            }
        }
        if (!ok) {
            return false;
        }
    }
    return true;
}

int current_patch_count() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_plan[i] != '.') {
            cnt++;
        }
    }
    return cnt;
}

void save_best_plan(int cnt) {
    best_count = cnt;
    for (int i = 1; i <= n; i++) {
        best_plan[i] = choose_plan[i];
    }
}

// 第 dep 层决定第 dep 个位置不种、种 G 草或种 H 草。
void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (current_plan_valid()) {
            int cnt = current_patch_count();
            if (cnt < best_count) {
                save_best_plan(cnt);
            }
        }
        return;
    }

    choose_plan[dep] = '.';
    dfs_choose(dep + 1);

    choose_plan[dep] = 'G';
    dfs_choose(dep + 1);

    choose_plan[dep] = 'H';
    dfs_choose(dep + 1);
}

void solve_case() {
    string s;
    cin >> n >> k;
    cin >> s;

    for (int i = 1; i <= n; i++) {
        cow[i] = s[i - 1];
        choose_plan[i] = '.';
        best_plan[i] = '.';
    }

    best_count = INF;
    dfs_choose(1);

    cout << best_count << '\n';
    for (int i = 1; i <= n; i++) {
        cout << best_plan[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

这个暴力把每个位置看成三种选择：不种、种 G、种 H。递归生成完整方案后，再检查所有牛是否能在距离 K 内找到同品种草。它能直接验证最优数量，但 $3^N$ 不能通过满分数据。

满分做法是从左到右贪心。

扫描到第 i 头牛时，如果它已经被最近的一块同品种草覆盖，就不需要新草。

如果它还没被覆盖，那么任何合法方案都必须为它新增一块同品种草。为了让这块草尽量覆盖后面的牛，应该把它放到最靠右且还能覆盖 i 的位置，也就是 i + K。

如果 i + K > N，说明已经到末尾附近了。此时把草放在 i 就能覆盖后面所有同品种牛；若 i 已经被另一种草占用，就放到 i - 1，仍然能覆盖到末尾。

实现时分别记录最近的 G 草和 H 草位置：

last_g_patch：最近一块 G 草；
last_h_patch：最近一块 H 草。

若当前是 G 牛且 i - last_g_patch > K，就新种一块 G 草；H 牛对称处理。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:15
 * update_at: 2026-07-11 17:16
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, k;
char cow[MAXN];
char answer_plan[MAXN];
int patch_count;

void place_patch(char c, int pos, int &last_patch) {
    int patch_pos;

    if (pos + k <= n) {
        patch_pos = pos + k;
    } else {
        patch_pos = pos;
        if (answer_plan[patch_pos] != '.') {
            patch_pos--;
        }
    }

    answer_plan[patch_pos] = c;
    last_patch = patch_pos;
    patch_count++;
}

void solve_case() {
    string s;
    cin >> n >> k;
    cin >> s;

    for (int i = 1; i <= n; i++) {
        cow[i] = s[i - 1];
        answer_plan[i] = '.';
    }

    int last_g_patch = -k;
    int last_h_patch = -k;
    patch_count = 0;

    for (int i = 1; i <= n; i++) {
        if (cow[i] == 'G' && i - last_g_patch > k) {
            place_patch('G', i, last_g_patch);
        }
        if (cow[i] == 'H' && i - last_h_patch > k) {
            place_patch('H', i, last_h_patch);
        }
    }

    cout << patch_count << '\n';
    for (int i = 1; i <= n; i++) {
        cout << answer_plan[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

复杂度

每组数据只扫描一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的贪心标准是：遇到第一个没被覆盖的牛时必须新种草，并把这块草放到尽量靠右的位置。

这个选择不会影响已经处理过的牛，同时让未来覆盖范围最大，因此可以得到最少草地数量。

目录

题意

思路

代码

复杂度

总结