Hướng dẫn giải của Đá thủ
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.
Nhận xét: Với ~4~ số ~x, y, z, t~ bất kì thỏa mãn ~x \le y~ và ~z \le t~, ta có: ~\max(x, z) + max(y, t) \le max(x, t) + max(y, z)~.
Không mất tính tổng quát, giả sử mảng ~a~ được sắp xếp tăng dần. Xét một cách sắp xếp bất kì của mảng ~b~, dựa vào nhận xét trên, ta có thể thấy rằng: nếu tồn tại hai vị trí ~i, j~ thỏa mãn ~i < j~ và ~b_i \le b_j~, ta có thể hoán đổi ~b_i~ và ~b_j~ để nhận được kết quả tốt hơn. Vì vậy, cách sắp xếp tốt nhất chính là sắp xếp mảng ~b~ giảm dần.
Mở rộng: Hãy giải bài toán trên với phiên bản ~m~ hàng thay vì ~2~ hàng.
Bình luận
Cho em hỏi, em cũng đã sắp xếp hai mảng theo thứ tự ngược lại(mảng a giảm dần, mảng b tăng dần), nhưng lại bị sai ở test #32, là sao vậy ạ?
Code của em: https://onlinegdb.com/SluBmUreZ
bạn thay r bằng long long là ac nhé
À. Cảm ơn anh/chị!