Codeforces - 1108D. Diverse Garland

Question

题目

这题和上题差不多，也是给你 n 个有 n 个字符的字符串，这里的 Diverse Garland 定义为任意两个相邻的字符不能相等，要你改变最少的字符，使得字符串是 Diverse Garland 。

解析

使用贪心+枚举即可:

• 从 1 ~ n-1 位置枚举，如果 str[i] == str[i-1] ，说明至少需要改变其中一个；
• 此时我们去看 str[i + 1] 的情况，此时贪心的思想就是让 str[i-1] 、str[i]、str[i+1] 这三个字符，只需要改变 str[i] 就能让 str[i-1]、str[i]、str[i+1] 三个字符组成的字符串是 Diverse Garland ；
• 具体的六种情况我在代码中都注释了，注意细节即可；

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        int n = cin.nextInt();
        String str = cin.next();
        char[] chs = str.toCharArray();
        int count = 0;
        for (int i = 1; i <= n - 1; i++) {
            if (chs[i] != chs[i - 1])
                continue;
            count++;
            if (chs[i] == 'R') {  // RRB -> RGB
                if (i + 1 < n && chs[i + 1] == 'B') {
                    chs[i] = 'G';
                } else { // RR(R|G) -> RB(R|G)
                    chs[i] = 'B';
                }
            } else if (chs[i] == 'B') {
                if (i + 1 < n && chs[i + 1] == 'R') { //BBR --> BGR
                    chs[i] = 'G';
                } else {  // BB(B|G) --> BR(B|G)
                    chs[i] = 'R';
                }
            } else { // chs[i] == 'G'
                if (i + 1 < n && chs[i + 1] == 'R') { //GGR --> GBR
                    chs[i] = 'B';
                } else {             // GG(G|B) --> GR(G|B)
                    chs[i] = 'R';
                }
            }

        }
        out.println(count);
        out.println(new String(chs));
    }
}