Easy choice

Pentru rezolvarea problemei, vom sorta mai întâi crescător şirul înălţimilor. Se poate observa uşor că o divizie va fi un interval compact în şirul sortat, de lungime C. Ne propunem să alegem R astfel de intervale care să nu se suprapună şi care să minimizeze dezechilibrul armatei.

Vom fixa printr-o căutare binară dezechilibrul D şi vom verifica dacă se pot plasa cel puţin R intervale disjuncte, fiecare cu dezechilibru cel mult D. Această verificare se poate realiza prin metoda programării dinamice, observând relaţia

  • A[i] = max(A[i - 1], A[i - C] + 1), dacă H[i] - H[i - C + 1] ≤ D
  • A[i] = A[i - 1], altfel

unde A[i] = numărul maxim de divizii cu dezechilibru cel mult D ce se pot crea folosind doar primii i candidaţi, iar H = şirul sortat al înălţimilor.

Complexitatea rezolvării de mai sus este O(N * log N + N * log H).