1815. Get the maximum number of groups of fresh donuts state compression

1815. Maximum number of groups to get fresh donuts

There is a donut shop that bakes batchSize doughnuts per batch.The shop has a rule that all doughnuts must be sold out before a new batch of doughnuts is baked.You are given an integer batchSize and an array of integers groups, where each integer in the array represents a group of customers who came to buy donuts, where groups[i] indicates the number of customers in this batch.Every customer happens to want just one donut.

When one group of customers arrives at the store, all of them must finish their doughnut purchases before the next group arrives.If the first customer in a group gets donuts that aren't left over from the previous group, then everyone in this group will be happy.

You can arrange the order in which each batch of customers arrives at will.Please return at most how many groups of people would be happy under this premise.

Example 1:

Input:batchSize = 3, groups = [1,2,3,4,5,6]Output:4Explanation: You can order these batches of customers as [6,2,4,5,1,3] .Then groups 1, 2, 4, and 6 will all be happy.

Example 2:

Input:batchSize = 4, groups = [1,3,2,5,2,2,1,6]Output:4

Tip:

• 1 <= batchSize <= 9
• 1 <= groups.length <= 30
• 1 <= groups[i] <= 1e9

Source: LeetCode
Link: https://leetcode.cn/problems/maximum-number-of-groups-getting-fresh-donuts
The copyright belongs to LeetCode.com.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Failure, no matter how it is timed out, it's a headache, I want to compress the state, but it's not convenient, the numbers are different

Method: State Compression

This problem is unequal-length state compression that has never been encountered before.What does that mean?That is, for example, the current number can be up to 5, then for this digit, its base number is 6, the full 6 is just the remainder of 0 to 5, the next largest number is 2, and the full 3 is just enough to enumerate 0 to 1.2, so there are a total of 6*3 possibilities for these two bits together, here is a number mapping: 7->[2,1] (2+1*5).This solves the problem of discontinuous enumeration.

The second question is how to get one of the numbers.Take the current decimal as an example: 120, the middle 2 is required, we can use 120%100/10 to take out the middle one, that is, the base that needs the next and current bits.So preprocessing calculates the value of each base, in particular, enumerates all the product values ​​by one more bit to prevent overflow

Specific steps:

1. Take the remainder of all numbers for statistics, and get the number corresponding to each remainder

2. Calculate the base of the remainder when reaching a certain digit

3. For every possible situation of binary enumeration, take out the specific value by taking the remainder and then rounding it up and sum it up

4. If the remainder is 0 in the front, the latter will be happy no matter what the result is, so if the remainder is 0, the result will be added by 1; if the remainder is not 0, the resultconstant.The enumeration can currently take any one of the values, they may be the last number, and take the best result.

5. Accumulate the result of the calculation, taking the maximum value into the answer.

6. In the previous steps, you can not count the part with the remainder of 0.Because the remainder is 0 must be happy.Values ​​with a remainder of 0 are accumulated directly into the answer.

class Solution {public int maxHappyGroups(int batchSize, int[] groups) {if(batchSize==1) return groups.length;int[] mods = new int[batchSize];for(int group:groups) mods[group%batchSize]++;int[]base = new int[batchSize+1];base[1]=1;for(int i = 2;i<=batchSize;i++){base[i]=base[i-1]*(mods[i-1]+1);}int total = base[batchSize];int ans = 0;int[] dp = new int[total];for(int i = 1; i < total; i++){int[] tms = new int[batchSize];int sum = 0;for(int j = 1; j 0){dp[i] = Math.max(dp[i-base[j]]+((sum-j)%batchSize==0?1:0),dp[i]);}}ans = Math.max(ans,dp[i]);}return ans+mods[0];}}