Cho em xin ý tưởng để làm bài toán sau ạ. Em cảm ơn.
Trường X cần đưa 𝑛 học sinh ra phục lễ khai mạc lễ A. Nhà trường có thể thuê xe buýt và taxi. Mỗi xe buýt chở được không quá 50 học sinh và giá thuê là 𝑎, mỗi taxi chở không quá 4 học sinh và giá thuê là 𝑏(𝑎 > 𝑏). Tất cả phải khởi hành đồng thời từ trường.
Yêu cầu: cho các số nguyên dương 𝑛, 𝑎 và 𝑏(1 ≤ 𝑛 ≤ 10^5; 1 ≤ 𝑏 < 𝑎 ≤ 10^3). Hãy xác định số xe buýt và số taxi cần thuê để tổng chi phí là nhỏ nhất.
input: dòng chứa 3 số nguyên 𝑛, 𝑎 và 𝑏.
output: số xe buýt và số taxi cần thuê.
Tính số xe bus + taxi cần thuê
Tôi thấy nếu a <= 12.5 * b thì tui ưu tiên chọn xe bus trước, còn sót lại bao nhiêu thì cho đi taxi 
1 Like
ví dụ như này:
Input: 4 3 2
Output: 0 1
thì 4 >= 12.5 * 3 vẫn chọn 1 taxi ạ :Đ
Nếu số HS >= 50 nữa thì chắc đúng nhỉ 
theo tui thì bài toán này là giải pt hoặc hệ pt nhưng vẫn chưa có ý tưởng gì 
Ồ, cách của tôi đưa ra có phần “tham lam” nên kết quả cuối cùng có thể không phải là tốt nhất.
Thử tìm cách khác vậy 
Nếu 0 < n <= 50 thì f(n) = min(a, ceil(n/4)*b)
Nếu n > 50 thì f(n) = min(f(n-50) + a, f(n-4) + b)
n <= 50 thì 1 là đi 1 chiếc xe buýt, 2 là đi n/4 chiếc xe taxi, vì nếu 1 buýt + k taxi thì mắc hơn 1 buýt rồi, vậy chỉ có thể đi 1 buýt hoặc toàn taxi nếu n <= 50
n > 50 thì đệ quy thôi :V có 2 cách để lên n hs: 1 là từ n-50 hs lên n bằng cách thêm 1 xe buýt, 2 là từ n-4 hs lên n bằng cách thêm 1 taxi. Lấy min 2 cái là được.
1 Like
Bài này t nghĩ khá khoai đấy, trường hợp 50em đi xe taxi vẫn rẻ hơn bus thì sao.
Đề bài chỉ cho a >b, chứ đâu có cho biết a/b = bn đâu
thanks bác để tui thử 
n=50 thì lấy min của 2 giá nhỉ tui nghĩ vậy 
vấn đề là ở đây
với n chưa đầy <= 105, thì số xe buýt cần thuê chỉ có thể là 0 1 2 3 mà thôi
chỉ có 4 case, mỗi case tính số xe taxi còn lại rồi so sánh chi phí của 4 case thôi
2 Likes
105 103 là 10^5 10^3 đó =] Do copy paste nên ko copy ^5 ^3 được. Bài toán rất thực tế 1 trường có 100 ngàn hs =]
3 Likes
bài này nếu thực sự cho dữ liệu lớn hơn thì vẫn là dễ
với mỗi 100hs, thì chắc chắn sẽ chọn 2 buýt hoặc 25 taxi, tùy giá bên nào rẻ hơn min(2a, 25b), bằng nhau thì any, nào cũng được, bài toán chỉ quan tâm chi phí
như vậy chỉ việc xử lý số lẻ còn lại là n%100, số này dưới 100, lại trở về bài toán trên chọn 0 1 2 buýt + taxi còn lại
4 Likes
cho mình hỏi là lỡ min của nó là 1 buýt và 7 taxi với mỗi 100hs thì sao bác
tính theo đầu người thì chi phí đi lại của mỗi người là
a/50 hoặc b/4
100 người thì chi phí sẽ là min(a/50, b/4)*100 = min(2a, 25b)
kết quả được tính dựa trên chi phí tối ưu nhất theo đầu người rồi, nên không có chuyện pha một ít a/50 với b/4 sẽ ra được con số nhỏ hơn đâu
4 Likes
cảm ơn bác rất nhiều vì thuật toán tôi hiểu rồi
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?