Stuck in a problem

Revision en1, by skpro19, 2017-09-24 22:49:13

The problem is this.

The editorial says this:-

We need some observation: There exists an optimal solution such that: in any pile, the box on the higher position will have a smaller strength.

Let k be the minimal number of piles, then there exists an optimal solution such that: The height of all piles is n/k or n/k+1 (if n%k=0, then all of them have the height n/k).

We can prove them by exchange argument: from an optimal solution, swap the boxes in it to make above property holds, and we can ensure it will remain valid while swapping. Then for a given k, we can check whether there exist a solution: the i-th (indexed from 0) smallest strength needs to be at least i/k. So we can do binary search (or just enumerate, since n is only 100) on k.

Doubt:

Why does the ith index need to be atleast i /k ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English skpro19 2017-09-24 22:49:13 895 Initial revision (published)