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).