Editorial for Tổng bộ ba

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.

Author: Yunan

Nguồn: CSES

Giả sử ta biết giá trị ở vị trí ngoài cùng bên trái trong tổng là $a_i$ ~a_i~. Khi đó, bài toán còn lại là tìm hai giá trị khác nhau trong đoạn con $a_{i+1}...a_n$ ~a_{i+1}...a_n~ có tổng bằng $x - a_i$ ~x - a_i~. Đây là một bài toán đơn giản hơn.

Dựa trên ý tưởng này, ta có thể duyệt qua tất cả các cách có thể chọn $a_i$ ~a_i~ và giải bài toán còn lại. Tuy nhiên, trước tiên ta sắp xếp mảng để có thể giải bài toán tìm hai giá trị có tổng bằng một giá trị cho trước trong $O(n)$ ~O(n)~ bằng kỹ thuật hai con trỏ (two pointers).

Do đó, thuật toán thu được có độ phức tạp $O(n^2)$ ~O(n^2)~.

Editorial for Tổng bộ ba

Comments