1815. 得到新鲜甜甜圈的最多组数

题目描述

有个店，每次出货量是b，且只有之前全卖完以后才继续出货
给了一个整数数组groups，元素ei是这一批顾客的人数，且每个人刚好只要一个
如果某批顾客的第一个顾客拿到的货是新出的，这批人就会开心
问怎么安排来着的顺序，尽量让开心的批次最大？

基本分析

1. 直白的翻译题意，开心值怎么算？对第i批顾客，需要前i-1批的和是b的倍数，这批就会开心
2. 如果数组长度不大于20，可以怎么做？定义状态mask表示当前状态时的最大满意度，枚举mask中1的位置，进行状态转移
3. 在数组长度30时候，考虑怎么预处理group，这样够不够？因为b<9,可以考虑把group转化为频次数组fq0，其中fq0[i]表示人数%9=i的组的组数，这样fq0的维度不会超过9，某个维度的值不会超过30。
4. 如果按照上面方式定义dp状态可行吗？每个坑可能有30中选择，共计9个坑，复杂度在\(30^9\),反而更大
5. 怎么进一步优化？定义一个特殊的进位方式，每一位的进制都是变化的，第0位是1, 第1位是(fq0[1]+1), 第2位是fq0[2]+1…。这样可以方便通过某个fq转化为mask，又能通过mask转化为对应的fq
6. 具体怎么实现这个进位机制？
   • 求出w数组，w[0]=1, w[1] = w[0] * (fq0[0]+1), w[2] = w[1] * (fq0[1]+1)…
   • 根据w数组和fq求出fq对应的掩码mask：mask = fq[0]w[0] + fq[1]w[1]+…
   • 根据mask反推出i位的fq[i]值：\(fq[i] = \frac{mask}{w[i]} \% (fq0[i]+1)\)。为什么能这么做，因为比i小的位置的值加起来的和会小于w[i],比i大的位置的fq[j]*w[j]里面的w[j]又能整除w[i], 所以可以得到该处的值（待证明）
7. 之后怎么处理？
   • 枚举mask，初始化当前和是0
   • 遍历mask所有位置，求出mask中第余i的组的组数fq[i],累加和的贡献fq[i]*i，记最后的和是cur
   • 枚举进行转移，如果mask中包含某个组（对应fq[i]>0) ,当把这个组的人放到队尾的时候，前面的和就是cur-i，前面组形成的表达就是mask-w[i], 如果之前的和%b是0，表示开心组+1，f[mask] = max(f[mask], f[mask-w[i]]+int(cur-i ==0))。需要注意的是这个转移可能会有多个。

代码

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        b = batchSize
        if b == 1:
            return len(groups)
        fq0, fq, w = [0] * b, [0]*b, [0]*b

        # 统计fq0
        for item in groups:
            fq0[item % b] += 1
        
        # 求w
        w[1] = 1
        for i in range(2, b):
            w[i] = w[i-1] * (fq0[i-1]+1)
        
        # 求mask上限
        nmask = 1
        for i in range(1, b):
            nmask = nmask * (fq0[i] + 1)
        
        # 定义dp数组
        f = [0] *nmask

        # 遍历
        for mask in range(1, nmask):
            # 求对应的人数%b
            cur = 0
            for i in range(1, b):
                fq[i] = int(mask / w[i]) % (fq0[i]+1)
                cur += fq[i] * i
            # 找状态去转移
            for i in range(1, b):
                if fq[i]:
                    cur = (cur + b - i) % b
                    f[mask] = max(f[mask], f[mask - w[i]] + int(cur ==0))
                    cur = (cur + i) % b
        
        return f[-1] +fq0[0]

复杂度

时间：\(nmask不会超过5 \cdot 10^5，加上每个状态枚举最多9次，总计不会超过4.5 \cdot 10^6\)
空间：\(存状态的开销，不超过5\cdot 10^5\)

总结

理解题意：能看出来是当前组i的情况由i之前所有组的和%b决定
转移思路：由于n比较大，想到预处理groups数组为频数数组
新的问题：频数数组的复杂度依然很高
新的表达方式：采用变进制的方式进行表达，实现数组-mask以及mask到数组的转化
继续规划：在以上新表达的基础上，枚举每个状态，根据状态枚举统计总和，在枚举每一位考虑（假设这一位在最后）建立转移过程。

原文地址：http://www.cnblogs.com/zk-icewall/p/16837374.html