Ý tưởng

Chặt nhị phân giá trị nhỏ nhất cuối cùng ~V~. Với một giá trị ~V~, lượng kẹo cần thêm để mọi hộp có ít nhất ~V~ viên là ~\sum \max(0,V-a_i)~. Sau khi tìm được ~V~ lớn nhất khả thi, nâng các hộp nhỏ hơn ~V~ lên ~V~ rồi rải phần dư từ trái qua phải cho các hộp đang có đúng ~V~ viên.

Độ phức tạp

M?i l?n ki?m tra m?t gi? tr? c?n ~O(n)~. Ch?t nh? ph?n tr?n ??p ?n n?n t?ng ?? ph?c t?p ~O(n \log M)~, v?i ~M~ l? mi?n gi? tr? k?o.