Hướng dẫn giải của [KHTN - TS10 - 2025] Bài 1: Điểm
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tóm tắt đề bài
Cho ~n~ đội, đội thứ ~i~ có chỉ số sức bền ~m_i~ và sức mạnh ~v_i~. Tổng sức ~t_i~ của đội ~i~ là ~m_i~ + ~v_i~. Hãy tìm chênh lệch giữa đội có tổng sức lớn nhất và đội có tổng sức bé nhất.
Lời giải
Ta tính ra mảng ~t_i~ là tổng sức của đội thứ ~i~. Ta sắp xếp mảng lại.
Kết quả sau khi sắp xếp mảng tăng dần sẽ là ~t_n - t_1~.
Ta cũng có thể lặp hai lần để tìm đội có tổng sức lớn nhất và bé nhất, sau đó lấy hiệu.
Độ phức tạp: ~O~ (~n \times log~ ~n~) hoặc ~O~ (~n~).
Bình luận