题解：CF746D Green and Black Tea

· · 题解

题面大意

Innokentiy 想要喝 n 杯茶，他有 a 杯绿茶和 b 杯红茶，相同的茶不能连续喝 k 次，请让我们确定合法的顺序。当不能达到时，输出 NO。

思路

题目传送门

我一开始想要用深搜，但是想了一下会超时，于是还是要使用贪心的思路。

当剩下的红茶数量比绿茶数量多时，尽可能的多用红茶，直到没有 k 包为止，然后使用一杯绿茶。绿茶同理。

什么时候无解呢？那就是当 \frac{a}{b+1}>k（这时不能用喝红茶和一杯绿茶的方式喝茶） 或者 \frac{a}{b+1}=k 且 a 除以 b 的余数为 k 时（同样的，不能用和绿茶+一杯红茶的方式喝茶），输出 NO。

此处可展示大致的无解以及考虑红茶的代码：

if (a/(b+1)>k || ((a/b+1)==k && a%b==k)) {
        cout<<"NO";
        return 0;
    }
    if (a==b) {
        for (int i=0;i<n;i++) {
            if (i%2==0) tea+='G';
            else tea+='B';
        }
    } 
    else if (a>b) {
        if (k==0) {
            cout<<"NO";
            return 0;
        }
        for (int i=0;i<n;i++) {
            if (i%(k+1)<k) {
                tea+='G';
                a--;
            } 
            else {
                tea+='B';
                b--;
            }
        }
        while (b>0) {
            tea+='B';
            b--;
        }
    } 
    //以下判断绿茶代码同理。