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.

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

Please read the guidelines before commenting.



  • 0
    bqvkhang  commented on May 14, 2023, 1:19 a.m. edit 2

    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


    • 3
      phanthai1601  commented on May 14, 2023, 4:34 a.m.

      bạn thay r bằng long long là ac nhé


      • 0
        bqvkhang  commented on May 14, 2023, 2:27 p.m.

        À. Cảm ơn anh/chị!