Codeforces Round #386 (Div. 2) D. Green and Black Tea 数论+贪心

My Solution

题意：喝掉n袋茶，其中a袋绿茶b袋红茶，连续喝相同的茶最多k次，如果可以全喝完则输出喝茶的序列，如果不能则输出NO

数论+贪心

char a为个数多的那个茶的字母的代表，同理b为少的那个字母，aa为a的个数，bb为b的个数

首先int realk = aa / (bb + 1); if(realk * (bb + 1) < aa) realk++; 如果 realk > k 则 ans 为 NO;

否则把aa 分成 bb + 1组，int ok = aa % (bb + 1);if(ok == 0){ok = bb + 1;}

从而有ok组是realk个a，剩余的是realk-1个a，每组间用b隔开。

复杂度 O(n)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

string ans;

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 6;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, k, a, b;
    cin >> n >> k >> a >> b;
    int aa = max(a, b), bb = min(a, b);
    char x, y;
    if(aa == a){
        x = 'G';
        y = 'B';
    }
    else{
        x = 'B';
        y = 'G';
    }

    int realk = aa / (bb + 1);
    if(realk * (bb + 1) < aa) realk++;

    if(realk <= k){

        //cout << realk << endl;
        int ok = aa % (bb + 1);
        if(ok == 0){
            ok = bb + 1;
        }
        int cnt = 0, oki = 0;
        ans.clear();
        for(int i = 0; i < n; i++){
            if(cnt == realk){
                ans += y;
                cnt = 0;
                oki++;
                if(oki == ok){
                    realk--;
                }
            }
            else{
                cnt++;
                ans += x;
            }
        }
        cout << ans << endl;
    }
    else cout << "NO" << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}