题目描述

OtterZ 决定用幽灵火制作一把武器。他收集了若干红色、绿色和蓝色的幽灵火。他将把一些幽灵火排成一排来制造武器。为了让武器发挥最大威力，OtterZ 将尽可能多地使用幽灵火，但如果在这一排中，有两个相同颜色的幽灵火相邻，或者它们之间恰好隔着两个幽灵火，武器就会失控。

形式化地说，OtterZ 收集了 r 个红色幽灵火、g 个绿色幽灵火和 b 个蓝色幽灵火。他希望构造一个由字符 ‘R’、’G’ 和 ‘B’ 组成的字符串 s，满足以下条件：

• 字符串 s 中 ‘R’、’G’ 和 ‘B’ 的出现次数分别不超过 r、g 和 b。
  
• 对于所有的$ 1 \le i \le |s|-1，s_i \neq s_{i+1}$。
  
• 对于所有的$ 1 \le i \le |s|-3，s_i \neq s_{i+3}$。
  
• 字符串 s 的长度最大。
  

请帮助 OtterZ 构造这一排幽灵火。虽然可能有多个满足条件的排列方式，OtterZ 只需要其中任意一个即可。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 t$ (1 \le t \le 10^4)$。接下来是测试用例的描述。

每个测试用例只有一行，包含三个整数 r、g 和 b$ (0 \le r, g, b \le 10^6，r+g+b > 0)$，分别表示红色、绿色和蓝色幽灵火的数量。

保证所有测试用例中 r+g+b 的总和不超过$ 10^6$。

输出格式

对于每个测试用例，输出一个由字符 ‘R’、’G’ 和 ‘B’ 组成的字符串 s。其中$ s_i $为 ‘R’、’G’ 或 ‘B’ 分别表示第 i 个幽灵火是红色、绿色或蓝色。

如果有多个最优答案，输出任意一个即可。

样例

输入样例

Plaintext

5
0 0 1
1 1 1
0 3 0
2 2 2
2 7 3

输出样例

Plaintext

B
RGB
G
GBRBRG
GRGRGBGBGBG

提示

• 对于第一个测试用例，”B” 是唯一有效的构造。
  
• 对于第二个测试用例，”RGB”、”RBG”、”GRB”、”BRG” 和 “BGR” 都是正确的。
  
• 对于第三个测试用例，”GG” 和 “GGG” 都是无效的，因为 s_1 = s_2，违反了相邻不能同色的规则。

思路

经验之谈，优先选最大的，接着选次大的，同时要符合条件要求$(s_i\neq s_{i-3} and s_i\neq s_{i-1})$，如果三者相等，那么优先选$s_i = s_i-2$,如果选不到，那就结束嘞！
时间复杂度O（n），模拟过去没问题，我学到了可以用一个数组遍历，找到当前最大值

代码

// Sunshine, sunshine, ladybugs awake!  
// Clap your hooves and do a little shake!  
#include <bits/stdc++.h>  
#define int long long  
//#define endl '\n'  
using namespace std;  
  
using PII=pair<int,int> ;  
using PIC=pair<int,char> ;  
inline static constexpr int MAXN=2010;  
inline static constexpr int mod=1e9+7;  
  
void solve() {  
    int a1,b1,c1;  
    cin>>a1>>b1>>c1;  
        vector<PIC> a={{a1,'R'},{b1,'G'},{c1,'B'}};  
    string s;  
    int cnt=0;  
    while(true){  
        int idx=-1;  
        for(int i=0;i<3;i++){  
            if(a[i].first==0)continue;  
                        if(cnt>=1&&s[cnt-1]==a[i].second)continue;  
            if(cnt>=3&&s[cnt-3]==a[i].second)continue;  
                        if(idx==-1)  
                idx=i;  
            else if(a[i].first>a[idx].first)  
                idx=i;  
            else if(cnt>=2&&a[i].first==a[idx].first&&a[i].second==s[cnt-2])  
                idx=i;  
        }  
        if(idx==-1)break;  
        a[idx].first--;  
        s+=a[idx].second;  
        cnt++;  
    }  
    cout<<s<<endl;  
}  
  
signed main() {  
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);  
    int t;cin >> t;while (t--)         solve();  
    return 0;  
}