Codeforces - 1108C. Nice Garland & 1108D. Diverse Garland 排列 | 枚举

Question

题目

给你 n 个有 n 个字符的字符串， Nice Garland 定义为任意两个位置 i、j 的字符，如果 |i - j| % 3 == 0 && str[i].color = str[j].color ，这个串就是 Nice Garland，给你一个字符串，要你改变最少的字符，重新组装字符串，使得字符串是 Nice Garland 。

解析

使用枚举 {'R', 'G', 'B'} 三个字符的排列，然后每次遍历数组，去组合字符串，看每次需要改变多少字符，取最小需要改变的一个即可。

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();
        char[] initArr = {'R', 'G', 'B'};
        char[] tmpArr = new char[3];
        char[] resPer = new char[3];
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                for(int k = 0; k < 3; k++){
                    if(i == j || j == k || i == k)
                        continue;
                    tmpArr[0] = initArr[i];
                    tmpArr[1] = initArr[j];
                    tmpArr[2] = initArr[k];
                    chs = str.toCharArray(); //注意每次都要用原来的 str
                    int count = 0;
                    for(int p = 0; p < n; p++){
                        if(chs[p] != tmpArr[p%3]){
                            count++;
                            chs[p] = tmpArr[p%3];
                        }
                    }
                    if(count < res){
                        res = count;
                        for(int p = 0; p < 3; p++)
                            resPer[p] = tmpArr[p];
                    }
                }
            }
        }
        out.println(res);
        for(int i = 0; i < n; i++)
            out.print(resPer[i%3]);
        out.println();
    }
}