Greedy? My approach:

First, for each index, decrease the number a(i-th) by r x times until the a(i-th) number is less than r. If a(i-th) is equal to 1, add 1 to a(i-th). Add x to the total number of tables needed.

For first sample inpuT, After this step, it should be like a[]=[2,2,3] and total number of tables=3 Then,sort the a[] in accending order. Followed by filling in the rest of the people, we match the index with a for-loop. For each for-loop, if the number is 0, simply ignore it.

if the number >= (r/2+1), we break the loop and check the number of indexes with is not equal to 0 and output(number oF table+number of indexes)

iF the number,say x, > 0 but < (r/2+1), we find the minimum matching index, say y, so that (x+y)<=r and y is not equal to 0.

if y does not exist, we break the loop and output as mentioned above.

if y exists, we set y=0, and set x=x+y, and find out more minimum matching indexes y' so that (x+y')<=r. If we find more y', set all y' to 0 and add it to x. If we cannot find more, we continue the for-loop.

if the for-loop runs til the end,output as mentioned above

Complexity: O(n^2)

But I think that the algorithm is not correct. Anyway at least for some cases it works ;)

Thanks a lot for replying. Interesting idea you have there, but I think it will fail for this case:

6 4 6 4 4 4

The correct output is 3, but I think your algorithm would produce 4 (please correct me if I'm wrong).

I tried n^2 dp with a greedy heuristic, but found some cases for which my code fails after getting Wrong Answer.