分发糖果问题

shaowu459

问题描述：

n（n为正整数） 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分，你需要按照以下要求，给这些孩子分发糖果
1）每个孩子至少分配到 1 个糖果。
2）相邻两个孩子评分更高的孩子会获得更多的糖果。
3）计算并返回需要准备的最少糖果数目 。

题目分析：

按照题目的分配原则，评分相同的孩子并不一定得到更多的糖果，每个孩子得到糖果的数量取决于这个孩子和其挨着的孩子评分比较结果。

假设孩子的评分数组是[1,3,2,2,1]，则将按以下方式分配糖果：
1）每个孩子先获得一颗糖果，每个孩子分配的糖果初始数组[1,1,1,1,1]。
2）第一个孩子评分是1，比右侧孩子评分3低，所以第一个孩子仍保留一个糖果，糖果数组不变，仍为[1,1,1,1,1]。
3）第二个孩子评分是3，比左侧的1分和右侧的2分都高，所以这个孩子可以加一颗糖果（因为要准备最少得糖果），糖果数组变成[1,2,1,1,1]。
4）第三个孩子评分是2，比左侧的3低，并且也不比右侧的2高，因此，糖果数组保持不变，仍为[1,2,1,1,1]。
5）第四个孩子评分是2，不比左侧的2高，但是比右侧的1高，因此这个孩子多一个糖果，糖果数组变成[1,2,1,2,1]。
6）第五个孩子评分是1，比左侧的2低，所以糖果数组保持不变。
7）最后比较一下评分数组和糖果数组：
评分数组：[1,3,2,2,1]
糖果数组：[1,2,1,2,1]
相邻每一个评分高的孩子糖果数量都更高一些，满足了题目所有要求，所以[1,2,1,2,1]就是结果数组。
8）因为是从左到右遍历每个孩子得到的结果数组，所以遍历一遍后可能不满足题目要求，这时就需要从右侧再往左侧遍历一遍，规则相同。只要注意一点，当第n个孩子比第n+1个孩子评分高时，在第n+1个孩子糖果的数量基础上+1得到的结果如果比当前第n个孩子的糖果数量还小，就仍保持第n个孩子的糖果数量即可，也就是取MAX(第n个孩子已有糖果数量，第n+1个孩子糖果数量+1)的结果。

shaowu459

此题目目前已有多种不同的公式，本帖主要介绍我自己使用的公式，先贴上公式如下：

1. =LET(v,A2:J2,f,LAMBDA(z,SCAN(,z,LAMBDA(x,y,IF(INT(y)>INT(x),MAX(INT(y)+MOD(x,1)+1%,y),y)))),SUM(--RIGHT(f(SORTBY(f(FILTER(v+1%,v<"")),-SEQUENCE(,COUNT(v)))),2)))

复制代码

公式中使用的核心函数是SCAN函数，因为SCAN函数的x只能返回单值，所以一般只能保留一个信息。在上面的公式中，使用“整数+小数”的方式构造x，整数部分是孩子的评分，小数部分是该孩子的糖果数量，因此x同时保留了评分和糖果数量两种信息，在后续运算时分别提取x的整数部分和小数部分则可分别运算，运算完毕后，再将整数部分和小数部分合并更新x值。

shaowu459

SCAN函数部分运算的主要过程如下：

1）遍历包含评分和糖果数量的数组，第一个孩子直接进入x的初始值。
2）循环第二个值时，取当前x（第一个孩子的评分+糖果数量数值）的整数部分（评分）和当前循环值整数部分比较，如果当前孩子的评分高，则取当前孩子的糖果数量和前一个孩子的糖果数量+1两者的最大值作为当前孩子的糖果数量，然后作为新x的小数部分，加上当前y值的整数部分，形成新的x。
3）直至循环完毕。

因为可能要调用两次，所以把这个SCAN函数部分定义为一个自定义函数f：

shaowu459

完整公式简要说明如下：

=LET(
    v, A2:J2,      源数据区域
    f, LAMBDA(z,   将SCAN函数运算定义为一个自定义函数f，以便重复调用
        SCAN(
            ,      省略一参，z的第一个值直接作为x的初始值，不参与LAMBDA函数体部分运算
            z,
            LAMBDA(x, y,
                IF(
                    INT(y) > INT(x),     如果当前孩子的评分大于前面一个孩子评分
                    MAX(INT(y) + MOD(x, 1) + 1%, y),     取前一个孩子糖果+1和当前孩子糖果数量较大者
                    y   如果当前孩子的评分不大于前面一个孩子，则保留糖果数量不变
                )
            )
        )
    ),
    SUM(
        --RIGHT(     因为直接使用MOD有浮点运算差，所以使用RIGHT函数取结果数组右侧两位（小数部分的糖果数量）再求和
            f(
                SORTBY(            从左到右遍历一遍后，将所有孩子倒序排列，再循环一次
                    f(FILTER(v + 1%, v < "")),   评分整数数组+0.01,给每个孩子先分一个糖果，然后调用f遍历
                    -SEQUENCE(, COUNT(v))
                )
            ),
            2
        )
    )
)

cxywz

利用整数部分和小数部分分别存储不同的结果。思路牛x。

静听溪流

前排点赞  支持

橒♂蝣

有点难，但看来想成高手LAMBDA是必须要学好啊

shaowu459

橒♂蝣 发表于 2023-12-8 17:03
有点难，但看来想成高手LAMBDA是必须要学好啊

这个题，就公式书写层面来说属于简单类的，我归到简单里了。题目本身分析出完整的解题思路难度比写公式要大一些。

cam333

牛逼，学习了

世界客都

WPS逐步逐步的发布了新函数，例如textsplit在最新版的wps也有了，看来没办法要跟着shaowu版主的步伐向前进了。