Packing chocolate boxes
The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as there are any chocolates left, fill a box with one of each of the chocolates. That solution is linear in the number of chocolate pieces but unfortunately not linear in the problem size. So instead of doing the greedy algorithm, we simulate how it would run and calculate how many boxes would be filled, in polynomial time. 

Let $x_i$ be the number of pieces of type $a_i$. Sort in descending order, then remove the chocolates where $x_i$ = 0. If n ≤ k you need $x_1$ boxes. 

As long as $x_k$ > $x_{k+1}$ you would put chocolates $a_1$ to $a_k$ into a box. This fills $x_k - x_{k+1}$ boxes, and you decrease $x_1$ to $x_k$ by $x_k - x_{k+1}$. You simulate this in constant time. 

After that you have $x_1$ to $x_j$ greater than $x_k$, and $x_{j+1}$ to $x_m$ equal to $x_k$, for some j &lt; k and m > k. So you have a larger number of j chocolates, and an equal number of m-j chocolates, m > k. You would fill m-j boxes by putting m-j of the chocolates $a_1$ to $a_j$ into each box, and filling with k-j of the chocolates $a_{j+1}$ to $a_m$. 

You would do that t times. t is limited: With each round of m-j boxes, the number of the top j chocolates is reduced by m-j, the next chocolates are reduced by k-j. The difference is reduced by t (m-k), so t ≤ $(x_j - x_{j+1}) / (m-k)$. The next chocolates are reduced by t (k-j), so t ≤ $(x_m - x_{m+1}) / (k-j)$, letting $x_{m+1} = 0$ if m = n. You take the largest possible t and simulate t (m-j) steps in constant time. 

When this is done (and t may be 0) we remove all chocolates with a zero count, and we may be done. If not, then we do one simulation step which will change the situation, and start all over. 

That's the idea. You can probably clean this up a bit.