天天看點

codeforces-1108C. Nice Garland-題解

題目: 

codeforces-1108C. Nice Garland-題解

 解題思路:

首先,采用暴力+枚舉的方法,列出六種可能出現的排列情況即("GRB","GBR","RGB","RBG","BGR","BRG");

然後,寫一個循環把這六種情況都算一下,看看與哪一種相似度最高(一樣的話随便,不影響結果),并記錄需要改的地方;

最後,将剛剛找到的比對可能循環輸出。

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int n;
    string s;
    cin>>n>>s;
    string str[6]={"GRB","GBR","RGB","RBG","BGR","BRG"}; //一共6種排列方式
    //注意str[]是二維數組 
	int ans,ansI;
    for(int i=0;i<6;i++){
        int cnt=0; //不相等字元的數量
        for(int j=0;j<n;j++){
            if(str[i][j%3]!=s[j])//核心! 
				cnt++;
		}
        if(cnt<ans)//如果cnt小,則将ans覆寫(題目要個數最少的) 
		{
            ans=cnt,//ans用來暫時統計cnt(即不相等的字元數量) 
			ansI=i;//ansI記錄i(str[]“6個”中的哪一個) 
		}
    }
    cout<<ans<<endl;
    for(int i=0;i<n;i++)
        cout<<str[ansI][i%3];
    cout<<endl;
	return 0;
} 
           

分析:

本人認為,此題的亮點在與“%3”,“二維數組”,“計次”上。(小編之前沒有想到)

采用暴力+枚舉(樣例較少),是此題變得較為簡單。

繼續閱讀