派分糖果

题目

派分糖果
定义说明：
最小值、最小值数组：
从数组最左边开始遍历，寻找第一个当前点<后一个点的点，如[2,1,3,1,1,4]，第一个满足最小值定义的点是1<3，即我们第一个最小值是1，那么与之对应的最小值数组就是[2,1];
进一步找最小值，我们可以看到[2,1]后面满足最小值的点是1<4，（注意：相同点也要算进去）所以这里最小值数组是[3,1,1]；
再继续找，因为已经到了数组最后，所以最小值就是4，最小值数组就是[4]。

例：[1,2,4,1,2]最少情况下每人分糖果数为[1,2,3,1,2]，这个就不说为什么这么分了。

整体思路（文字版）：

我们用一个辅助数组res，来保存每一个人需要分到的糖果数。遍历找原数组中最小值
最小值然后判断是否是整个数组第一个最小值
若该最小值是数组的第一个最小值，我们直接将这个最小值下标处的人分到的糖果置为1，存入res，然后从这个最小值下标倒着遍历到数组下标0处，如[3,2,1,4]，第一个最小值是1，res先存入1，然后我们从1倒着遍历到数组开头，res中保存每个分到的糖果数便为[1,2,3]。
若不是第一个最小值，判断其是否和前一个最小值紧挨着
4.1 若紧挨着，我们就将这个最小值分到的糖果直接置为前一个最小值分到糖果的数目+1，接着找下一个最小值，如[3,2,1,2]，这个数组的最小值就是1和2，1和2紧挨着
4.2 若不紧挨着，此时要对这个最小值数组进行进一步判断，因为有可能最小值数组内是同一权重。如[3,1,2,2]，第二个最小值数组是[2,2]
4.2.1 若数组内是同一权重，那么我们就需要将当前最小值数组[2,2]的最小值所分到的糖果置为前一最小值所分到糖果数+1，也就是例子[3,1,2,2]中最小值1分到糖果数1，最小值2分到糖果数为2
4.2.2 若数组内不是同一权重，那么此时最小值分到糖果数就能置为1，然后是倒着为每个最小值数组里的权重分糖果
注意4.2.2的情况，最小数组内不是同一权值的情况，我们最后还要再进行一下判断，因为有这种情况的发生[5,4,1,3,3,5,1]，按照最小值进行切分原数组为[5,4,1]—[3,3]—[5,1]，我们按照4.2.2进行糖果数保存时，我们将[5,1]中的1保存的糖果数是1，那么根据之前倒查最小数组加糖果的逻辑，5就应该分到2个糖果。但是，要注意到原数组中5比其前面的3大，它分到的糖果肯定要比3多，而3我们可以由之前的逻辑推知其分到的糖果数为2，所以这里就产生了错误。解决的办法就是我们对res[-1]也就是5分到的糖果数进行更新，将其更新为（4.2.2中5分到的糖果数2）和（前一个最小值3分到糖果数+1=3）的最大值，也就是res[-1]=2更新为res[-1]=3。

思路图例：

具体代码为：

a= [2,3,4,1,5,6,2,1]
def send(nums):
    m=len(nums)
    i=0
    #辅助数组
    res=[]
    while i<len(nums):
        #从此处开始找最小值
        #此处定义j，k。j是为了遍历找当前最小值，k是为了作比较，来判断我们找到的最小值是否和前一个最小值紧邻
        j=k=i	
        while j<len(nums)-1 and nums[j]>=nums[j+1]:
            #j是最小值的下标，此处我把相等的数也计算上了，比如[5,4,1,1,2]，我计算的最小值下标是3而不是2
            j+=1
        
        #找到最小值后
        
        #1.最小值不紧邻
        if j!=k:
            
            #此处我们先将最小值分的糖果存入糖果序列，再倒着保存其他的
            
            #数组内权重相同，保存的最小值糖果数肯定要大于前一个最小值的糖果数（res[-last_point]+1），后文有解释
            if nums[k]==nums[j]:
            	res.append(res[-last_point]+1)	
            #数组内权重不同，直接置1
            else:
            	res.append(1)	
            
            
            #此处倒着遍历最小数组内的权重，因为最小值保存过了，所以我们从最小值前一个下标处倒着遍历
            n=j-len(nums)-1	
            
            #将当前找到最小值的权值进行保存，来判断数组中每个权重分到的糖果数
            now_weight=nums[j]
            while n>=k-len(nums):
            	#权重相同
                if nums[n]==now_weight:
                    res.append(res[-1])
                #权重不同，将now_weight更新为当前点的权值
                elif nums[n]>now_weight:
                    now_weight=nums[n]
                    res.append(res[-1]+1)
                n-=1
                
            #此处是为了针对5中我们所提到的 [5,4,1,1,5,6,3,2,1,3]情况提出的解决办法
            if nums[k]>nums[k-1]:
            	#因为last_point还没有更新，所以我们可以通过它和当前最小值数组长度来定位到res中
            	#前一个最小值分到的糖果数
                res[-1]=max(res[-last_point-j+k-1]+1,res[-1])
        
        #2.最小值紧邻
        else:
        	#当找到数组第一个最小值时，糖果数直接置1
            if j==0:
            	res.append(1)
      		#非数组第一个最小值时，注意这是最小值紧邻情况
            else:
            	res.append(res[-last_point]+1)
            
        #该变量是为了记忆前一个最小值数组长度，这样我们就可以通过res[-last_point]找到前一个最小值分到的糖果数
        last_point=j-k+1 
        
        i=j+1	#寻找下一个最小值
        
        #这里的print是为了使每一个最小值更明显，让编程者更好的调试和理解，正常答题需要删掉
        print(res)
    
    #我们将糖果序列的和求出来即是最后的结果
    return(sum(res))
        

print(send(a))

派分糖果

派分糖果

题目

整体思路（文字版）：

思路图例：

具体代码为：

相关推荐