Dạng bài tập này em không nắm được và cũng không tìm thấy nhiều hướng dẫn, mong mọi người giúp em ạ, em có một đề dạng như vậy dưới đây, mong được hướng dẫn cụ thể ạ
Nhờ hướng dẫn dạng bài tập chia các số trong dãy theo yêu cầu
A post was split to a new topic: Nhờ hướng dẫn bài tập tối ưu di chuyển trên trục toạ độ
1 topic chỉ hỏi 1 bài thôi nhé.
Nhìn test và đề bài có nói “số lượng em được tặng nhiều nhất là nhỏ nhất có thể”, “mỗi em chỉ được nhận những hộp quà có màu giống nhau”, ta dễ dàng thấy chiến lược ở đây là chia đều số hộp quà cùng màu cho mỗi em.
Tư tưởng là vậy, không cần thuật toán gì cao siêu cả. Vấn đề là chia đều như thế nào.
Xét bổ đề: Chia đều k gói quà cùng màu cho n em, sao cho người nhận được nhiều quà nhất có số lượng nhỏ nhất có thể.
Đặt q = \lfloor \dfrac{k}{n} \rfloor,\ r = k \mod n \Rightarrow nq + r = k.
Chiến lược chia đều tốt nhất là r em nhận được q + 1 gói quà, n - r em còn lại nhận được q gói quà.
Kiểm tra lại: r(q+1) + (n-r) q = r + nq = k (đúng).
Áp dụng cho bài toán này, ta cũng cố gắng chia đều nhất có thể. Tuy nhiên có 1 trường hợp rất tệ, là không thể bổ đều số quà cho các học sinh (như bổ đề trên) được.
5 2
1 14
Đáp số của test này là 4.
Bài này áp dụng chặt nhị phân theo số hộp quà của người nhiều nhất.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?