Блог пользователя skpro19

Автор skpro19, история, 7 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится