Editorial for Giải cứu công chúa

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Gọi $sum$ ~sum~ là tổng các giá trị $A_i$ ~A_i~ của mảng và $max$ ~max~ là giá trị $A_i$ ~A_i~ lớn nhất. Xét hai trường hợp:

$sum \le max$ ~sum \le max~: Cần thực hiện $max$ ~max~ lần thao tác.
$sum > max$ ~sum > max~: Cần thực hiện $\lceil \frac{sum}{2} \rceil$ ~\lceil \frac{sum}{2} \rceil~ lần thao tác.

Độ phức tạp: $O(N)$ ~O(N)~

Editorial for Giải cứu công chúa

Comments