Editorial for Đá thủ
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments
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ị!