*Series đề lập trình NVT* Đề gốc: Chú của hai bạn An và Bình vừa đi xa về có đem theo một bao kẹo to gồm n gói kẹo, gói thứ i có a[i] viên kẹo. Chú không muốn làm hai bạn buồn nên muốn chia sao cho số kẹo chên lệch là ít nhất. Input: + n là số gói kẹo (1<=n<=10^6) + Dãy a là số viên kẹp trong từng gói (1<=a[i]<=100) Output: + Số kẹo chênh lệch ít nhất. Update: Sau khi nhận được đáp án từ bạn miruyo, hai bạn rất biết ơn. Nhưng hai bạn vẫn chưa biết mình nhận các gói kẹo nào. Bổ sung ouput: + Các gói kẹo của An + Các gói kẹo của Bình. * In theo thứ tự ban đầu.

Ý tưởng:

Do a[i] <= 100 nên chỉ có tối đa 100 giá trị phân biệt, vì vậy ta chia đều các gói kẹo có số kẹo bằng nhau đều cho 2 bên, có thể thực hiện trong O(n). Số lượng gói kẹo còn lại cần xét trong dãy bây giờ chỉ còn <= 100. Đến đây tổng của số kẹo còn lại cần phải chia (gọi là sum) chỉ còn lại trong khoảng 100*100 = 1e4, ta sử dụng mảng dp[i] với ý nghĩa kiểm tra xem từ tổng số kẹo hiện tại (sum <= 1e4) có thể chia sao cho 1 người nhận được số kẹo i hay không, thao tác này mất O(100.sum) với 100 là số lượng gọi kẹo còn lại cần chia. Số kẹo chênh lệch ít nhất cần tìm chính là ans = Min{abs((sum - i) - i)}. Để ý luôn có thể chia sao cho số kẹo chênh lệch <= 100 (dễ dàng chứng minh được), vì vậy ta xét hết số kẹo chênh lệch từ 0->100 và cập nhật ans mỗi lần xét, thực hiện trong O(100).

Thao tác in ra số kẹo của mỗi bạn thì dễ r, cho vào vector hay gì đó rồi in ra là được.

Độ phức tạp: O(n + 100.sum + 100) ≈ 1e6 phép tính, 1s là quá đủ hehe.