C++算法题:喂奶牛(谁能帮我做一下,急!)

Question

Feeding the Cows
Farmer John 有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1-N。
由于奶牛们都饿了，FJ 决定在 1-N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

每头奶牛愿意移动至多 K（0≤K≤N−1）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

输入格式：
每个测试用例包含 T 个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T 个子测试用例。
每个子测试用例的第一行包含 N 和 K。第二行包含一个长度为 N 的字符串，其中第 i 个字符表示第 i 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

输出格式：
对于 T 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 N 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 i 个字符表示第 i 个位置，若不种草则为 'A'，若种植喂饱更赛牛的草则为 'G'，若种植喂饱荷斯坦牛的草则为 'H'。任何合法的方案均可通过。
输入样例：

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

输出样例：

5
GHHGG
3
AGHAG
2
AAGHA
2
AAAGH
2
AAAHG
2
HG

注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：

AGHAA

这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 3 个位置以内。

测试点性质：
测试点 2-4 满足 N≤10。
测试点 5-8 满足 N≤40。
测试点 9-12 满足 N≤105。

希望各位帮忙给出代码,急用啊!

Answer 1

下面是一种使用贪心算法的 C++ 代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int t, n, k;
char s[N];

int main()
{
    scanf("%d", &t);
    while (t -- )
    {
        scanf("%d%d", &n, &k);
        scanf("%s", s + 1);

        int res = 0, last = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (s[i] != s[last]) res ++ , last = i;
            else if (i - last > k) res ++ , last = i;
        }
        printf("%d\n", res);

        last = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (s[i] != s[last])
            {
                putchar(s[last]);
                last = i;
            }
            else if (i - last > k)
            {
                putchar(s[last]);
                last = i;
            }
        }
        putchar(s[last]);
        puts("");
    }

    return 0;
}

算法流程：

1. 输入测试用例数量 t。
2. 对于每个测试用例，输入奶牛数量 n 和移动距离 k。
3. 输入字符串 s，表示每头奶牛的品种。
4. 初始化结果 res 为 0，表示种植草地的数量，初始化变量 last 为 0，表示上一个种植草地的位置。
5. 遍历字符串 s。

• 如果当前位置的字符与上一个位置的字符不同，则 res 加 1，last 赋值为当前位置。
• 否则，如果当前位置和上一个位置的距离大于 k，则 res 加 1，last 赋值为当前位置。

1. 输出 res。
2. 初始化变量 last 为 0，表示上一个种植草地的位置。
3. 遍历字符串 s。

• 如果当前位置的字符与上一个位置的字符不同，则输出上一个位置的字符，last 赋值为当前位置。
• 否则，如果当前位置和上一个位置的距离大于 k，则输出上一个位置的字符，last 赋值为当前位置。

1. 输出最后一个位置的字符。