Tóm tắt đề bài: bạn có N chiếc xe và cần phải bán hết N chiếc xe đó, mỗi năm chỉ được bán 1 chiếc. Chiếc xe thứ i có giá P[i] đồng, sau mỗi năm thì giá của mỗi chiếc xe sẽ giảm đi 1 đồng. hãy tìm cách bán sao cho đến khi bán xong chiếc xe cuối cùng bạn sẽ thu về được nhiều tiền nhất.
Hướng dẫn giải: Phương pháp tham lam. Cách tốt nhất để bán hết xe và nhận về lợi nhuận cao nhất chính là sắp xếp xe theo giá giảm dần rồi bán từ từ, chú ý trường hợp giá xe tụt xuống < 0 thì sẽ tính là = 0.
Chú ý: với các phép toán có sử dụng modulo:
Phép cộng: (a + b) mod c = ((a mod c) + (b mod c)) mod c
Phép trừ: (a - b) mod c = ((a mod c) - (b mod c)) mod c
Phép nhân: (a * b) mod c = ((a mod c) * (b mod c)) mod c
No comments:
Post a Comment