记一次失败的双周赛

赛后

让我唠唠

这次的双周赛，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很菜，我是真的很

谢谢，上面这是AI给我写的。不过也是实话，giao , byd😡还挺懂我是吧

昨天，双十一，秋风萧瑟，哥们儿一个人搁寝室独自力扣单排双周赛。第二题坐牢。

啊，平常卡三四也理解，第二想着怎么优化就是不行(~~不排除是白天xdoj写多了降智~~)

来题：给小朋友们分糖果II

正文

当时因为放在第二题，数据规模比第一题要高，所以我估摸着直接开第二题，弄完再开三四，好家伙，直接给我卡这儿了

第一题

~~先来水一下~~

链接：给小朋友们分糖果I

数据规模很小，所以实际上可以双层for直接暴力过

class Solution {
    public int distributeCandies(int n, int limit) {
        int res = 0;
        for(int num1 = 0 ; num1 <= limit ; num1 ++){
            for(int num2 = 0 ; num3 <= limit ; num3 ++){
                if(n - num1 - num2 >= 0 && n - num1 - num2 <= limit){
                    res ++;
                }
                // 没啥好说的，只需要三个人的数据都在 0~limit 之间即可
            } 
        }
    }
    return res;
}

第二题

我的想法

kid : 小朋友

candy : 糖果数量

因为是给3个小家伙分，所以考虑的情况是很少的，我就想着首先kid1拿，然后kid2，再是kid3，所以初始状态就是：

1
2
3

int candy1 = Math.min(n, limit);
int candy2 = Math.min(n - candy1, limit);
int candy3 = Math.min(n - candy1 - candy2, limit);

现在起始状态有的，肯定是 $ candy1 \geq candy2 \geq candy3$，所以我想的维持这个状态，这样只需要看这三个糖果数是哪种情况：

$ a, a, a $
$ a, a, b $ 或者 $ a, b, b $
$ a, b, c $
可以假想成各个情况下，糖果的分法

第一种情况，那么就是$A_3^0 = 1$
第二种，$A_3^1 = 3$
第三种，$A_3^2 = 6$
写一个方法或者函数来判断当前处于哪种情况，然后累加即可

但是，它这个分配策略太繁琐了，有

candy1 -> candy2
candy1 -> candy3
candy2 -> candy3
调了很久没想明白(应该有dp的思想)，加上交了几发都错了，就寄啦😝

学来的(对，我就是剽窃智慧doge)

每次赛后都习惯看看榜前面的Java代码，然后~~给自己一巴掌~~复盘

其实可以这样想：

首先，$ candy1 $从$ 0 $开始迭代，终止条件为$ \leq limit $ 和 $\leq n$，
然后剩下的先给$ candy2 $，

如果$ candy2 \leq limit $ ，那这种策略下分配方式是$ candy2 + 1 $
如果$ candy2 > limit $，那就令$ candy2 = limit $，然后剩下的再减去$limit$，再给$ candy3 $这种策略下分配方式是$ limit - candy3 + 1 $

关于分配方式，这里只需要看$ candy2 $ 和 $ candy3 $，二者在满足条件的情况下分配方式是$ candy2 - candy3 + 1 $

所以代码可以这样：

class Solution {
    public long distributeCandies(int n, int limit) {
        long res = 0;
        for(int num1 = 0 ; num1 <= limit && num1 <= n; num1 ++){
            int rest1 = n - num1;
            if(rest1 <= limit){
                res += rest1 + 1;
            }
            else {
                //int num2 = limit ;
                /**
                 * 这里把num2 直接省掉了，
                 * 因为num2 已经被赋值为limit了，
                 * 所以这里直接用limit 即可
                */
                int num3 = rest1 - limit;
                if(num3 <= limit){
                    res += limit - num3 + 1;
                }
            }
        }
        return res;
    }
}

挺好理解的，就是按常规的枚举来的实际上。用不着看糖果数来算方案。

ε=(´ο｀*)))唉，每次都是第二题想复杂，不需要其实。

还有，下次写公式记得在front-matter里开一下mathjax，还为这找了会儿bug😠