*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
*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
Lời giải 1 :
Ý 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.
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 10
Lớp 10 - Năm thứ nhất ở cấp trung học phổ thông, năm đầu tiên nên có nhiều bạn bè mới đến từ những nơi xa hơn vì ngôi trường mới lại mỗi lúc lại xa nhà mình hơn. Được biết bên ngoài kia là một thế giới mới to và nhiều điều thú vị, một trang mới đang chò đợi chúng ta.
Nguồn : ADMIN :))Xem thêm tại https://loigiaisgk.com/cau-hoi or https://giaibtsgk.com/cau-hoi
Copyright © 2021 HOCTAPSGK