Bình luận

• 
  

  2

  

  vudinhlong  đã bình luận lúc 30, Tháng 9, 2024, 14:55 ← chỉnh sửa →

  Comment này spoil thuật:

  Trước hết, ta sẽ chia ~n~ dự án thành ~2~ loại:

  • Loại ~1~: có lãi (tiền vốn ít hơn tiền công).
  • Loại ~2~: bị lỗ (tiền vốn nhiều hơn tiền công).

  Sau đó, ta tiến hành "tham lam" bằng cách sắp xếp lại theo tiêu chí như sau:

  • Gọi ~f_i~ là hiệu của tiền vốn - tiền công của phần tử thứ ~i~ đó.

  • Đối với các dự án lãi ~(f_i < 0)~, đương nhiên ta cần thực hiện chúng trước các dự án lỗ ~(f_i > 0)~. Còn so sánh các dự án lãi với nhau, thì ta cần tối ưu vốn bằng cách thực hiện các dự án lãi có số vốn bỏ ra ít hơn (vì đằng nào cũng lãi, nên cần sử dụng vốn tiết kiệm :D).
  • Đối với các dự án lỗ ~(f_i > 0)~, đương nhiên ta cần thực hiện chúng sau các dự án lãi ~(f_i < 0)~. Còn so sánh các dự án lỗ với nhau, thì ta cần tối ưu vốn bằng cách thực hiện các dự án lỗ đem lại tiền công nhiều hơn (vì đằng nào cũng lỗ, nên cần thu lại càng nhiều tiền càng tốt :D).

  • Cuối cùng là tìm ra số vốn ít nhất cần chuẩn bị bằng phương pháp tìm kiếm nhị phân.
  • Ta sẽ chặt trên đoạn ~[1, 1e9]~, với mỗi biến mid tính được, ta sẽ kiểm tra xem khi duyệt từ đầu tới cuối ~n~ dự án, có dự án nào không thực hiện được thì phải tăng số vốn lên; nếu thoả mãn thì thử giảm bớt số vốn xem còn số vốn nào ít hơn vẫn thoả mãn hay không :D

  -> Code AC <-

  Lưu ý: bản bài nộp tốt nhất là của thg bạn mình nó đấm :D