题目描述

难度分:$1500$

输入$n$，$k(1 \leq k \leq n \leq 10^5)$，$a$，$b(0 \leq a,b \leq n,a+b=n)$。

构造一个长为$n$的字符串，包含$a$个G和$b$个B，且不能有长度超过$k$的连续相同字母。

如果无法构造，输出NO，否则输出任意一个符合要求的字符串。

输入样例$1$

5 1 3 2

输出样例$1$

GBGBG

输入样例$2$

7 2 2 5

输出样例$2$

BBGBGBB

输入样例$3$

4 3 4 0

输出样例$3$

NO

算法

贪心构造

先消耗多的那个字母，不妨设多的字母为G，G和B交替构造。每次拿出来$k$个（在不合法的边缘疯狂试探）G，紧接着拿出一个B接在后面，交叉消耗两者构造出一个$temp$串，直到把G消耗完。

检查B还有没有剩下的，有就插到$temp$串中B所在的位置，也是尽量一次加到$k$个B连续，直到把B消耗完。这里在实现的时候不要直接往$temp$串中插入字符，这样时间复杂度会达到$O(n^2)$，选择直接构造一个新串$ans$。

最后$ans$仍然有可能是不合法的，检查一下，合法就输出它，不合法就输出NO。B多G少的情况也一样，对称分析就好了。

复杂度分析

时间复杂度

本质上就是循环遍历了$a+b=n$级别的次数，时间复杂度为$O(n)$。

空间复杂度

除了最终要打印的$ans$串，还处理出来了一个同规模的中间串$temp$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int n, k, a, b;

bool check(string& s) {
    int cnt = 1;
    char c = s[0];
    for(int i = 1; i < n; i++) {
        if(s[i] == c) {
            cnt++;
            if(c == 'G' && cnt > k) return false;
            if(c == 'B' && cnt > k) return false;
        }else {
            cnt = 1;
            c = s[i];
        }
    }
    if(c == 'G' && cnt > k) return false;
    if(c == 'B' && cnt > k) return false;
    return true;
}

void solve(int a, char c1, int b, char c2) {
    string temp;
    while(a) {
        if(a >= k) {
            temp += string(k, c1);
            a -= k;
            if(b) {
                temp.push_back(c2);
                b--;
            }
        }else {
            temp += string(a, c1);
            a = 0;
        }
    }
    string ans;
    for(int i = 0; i < temp.size(); i++) {
        ans.push_back(temp[i]);
        if(temp[i] == c2) {
            if(b >= k - 1) {
                b -= k - 1;
                for(int j = 0; j < k - 1; j++) {
                    ans.push_back(temp[i]);
                }
            }else {
                for(int j = 0; j < b; j++) {
                    ans.push_back(temp[i]);
                }
                b = 0;
            }
        }
    }
    while(ans.size() < n) {
        ans.push_back(c2);
    }
    if(check(ans)) cout << ans << endl;
    else cout << "NO" << endl;
}

int main() {
    scanf("%d%d%d%d", &n, &k, &a, &b);
    string ans;
    if(a > b) {
        solve(a, 'G', b, 'B');
    }else {
        solve(b, 'B', a, 'G');
    }
    return 0;
}