[USACO2022-DEC-Bronze] T2 Feeding the Cows 题解

一、题目描述

Farmer John has N (1≤N≤10^5) cows, the breed of each being either a Guernsey or a Holstein. They have lined up horizontally with the cows occupying positions labeled from 1…N.

Farmer John 有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions 1…N. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

由于奶牛们都饿了，FJ 决定在 1…N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。

Each cow is willing to move a maximum of K (0≤K≤N−1) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

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

输入

INPUT FORMAT (input arrives from the terminal / stdin):

Each input contains T test cases, each describing an arrangement of cows. The first line of input contains T (1≤T≤10). Each of the T test cases follow.

每个测试用例包含 T 个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T 个子测试用例。

Each test case starts with a line containing N and K. The next line will contain a string of length N, where each character denotes the breed of the ith cow (G meaning Guernsey and H meaning Holstein).

每个子测试用例的第一行包含 N 和 K。第二行包含一个长度为 N 的字符串，其中第 i 个字符表示第 i 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。

输出

OUTPUT FORMAT (print output to the terminal / stdout):

For each of the T test cases, please write two lines of output. For the first line, print the minimum number of patches needed to feed the cows. For the second line, print a string of length N that describes a configuration that feeds all the cows with the minimum number of patches. The ith character, describing the ith position, should be a '.' if there is no patch, a 'G' if there is a patch that feeds Guernseys, and a 'H' if it feeds Holsteins. Any valid configuration will be accepted.

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

样例

输入

复制

6

5 0

GHHGG

5 1

GHHGG

5 2

GHHGG

5 3

GHHGG

5 4

GHHGG

2 1

GH

输出

复制

5

GHHGG

3

.GH.G

2

..GH.

2

...GH

2

...HG

2

HG

说明

Note that for some test cases, there are multiple acceptable configurations that manage to feed all cows while using the minimum number of patches. For example, in the fourth test case, another acceptable answer would be:

.GH..

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

.GH..

This corresponds to placing a patch feeding Guernseys on the 2nd position and a patch feeding Holsteins on the third position. This uses the optimal number of patches and ensures that all cows are within 3 positions of a patch they prefer.

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

SCORING:

• Inputs 2 through 4 have N≤10.

• Inputs 5 through 8 have N≤40.

• Inputs 9 through 12 have N≤10^5.

测试点性质：

• 测试点 2-4 满足 N≤10。

• 测试点 5-8 满足 N≤40。

• 测试点 9-12 满足 N≤10^5。

二、分析

1. 定义放G草和H草的位置，如果牛的位置为i，草的位置可以覆盖到牛的话，就不用种草，否则要种草。

2. 草要尽量往右重，尽可能少地种草。

3. 如果当前没有种草，直接种草即可，否则再往前找种草的位置。

例1：

rightH	1	2	3	4	5
5,1	G	H	H	G	G
rightG
i=1	.	G	.	.	.	i=1的G可以吃到i+k的草,rightG更新为种草的位置，这个草还可以覆盖到rightG+k位置
		rightG

例2：

2，1	G	H
i=1	.	G				i=1的G可以吃到i+k的草,rightG更新为种草的位置，这个草还可以覆盖到rightG+k位置
i=2						i=2的H可以吃到i+k的草,i+k>n，所以最大种草位置为n，但是此位置已经有草了，往前找位置种草

三、代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char cow[N],ans[N];
int main() {int t; cin >> t;while (t--){memset(ans,'.',sizeof(ans));int ansCnt=0,rightH=0,rightG=0;int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>cow[i];if(cow[i]=='H'){if(i<=rightH)continue; //rightH可以覆盖这个H牛for(int j=min(n,i+k);j>=max(1,i-k);j--){//找到尽量右边的位置进行种草[i-k,i+k]为可以覆盖此奶牛的种草位置if(ans[j]=='.'){ans[j]='H';ansCnt++;rightH=j+k;//更新草的位置break;}}}else{if(i<=rightG)continue;for(int j=min(n,i+k);j>=max(1,i-k);j--){if(ans[j]=='.'){ans[j]='G';ansCnt++;rightG=j+k;break;}}}}cout<<ansCnt<<endl;for(int i=1;i<=n;i++){cout<<ans[i];}cout<<endl;}return 0;
}