Editorial for Tập xe


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.

Authors: jumptozero

Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên, ta có nhận xét rằng, việc sắp xếp lại thứ tự các phần tử của mảng theo thứ tự tăng dần không làm ảnh hưởng đến kết quả của bài toán !

Tiếp theo, ý tưởng của bài này là sử dụng tìm kiếm nhị phân như sau:

  • Ta có: \(a_i+a_j\le (\text{ }0\le i<j<n)\implies a_j\le m-a_i(\text{ }0\le i<j<n)\)

Gọi \(P(j,i)\) là số phần tử \(a_j\) thoả mãn \(a_j\le m-a_i\)\(Q(j,i)\) là số phần tử \(a_j\) thoả mãn \(a_j>m-a_i\)

Khi đó ta có: \(P(j,i)+Q(j,i)=n-i+1 (\text{ với }0\le i<j<n)\).

Và để tính được \(Q(j,i)\) ta sử dụng chặt nhị phân để tìm. Và sau khi tính được \(Q(j,i)\) ta dễ dàng suy ra được \(P(j,i)\)

Và kết quả của bài toán chính là: \(\sum\limits_{0\le i<j<n}P(j,i)\)

Độ phức tạp của bài toán là: \(O(nlog(n))\)

Các bạn có thể tham khảo code tại đây: Link

Chú ý: Ở trong code của mình có sử dụng hàm: upper_bound, chính là hàm tìm kiếm nhị phân, các bạn có thể tự tìm hiểu thêm về những hàm tương tự như: lower_bound,...

Ps: Nếu có gì thắc mắc, các bạn cứ comment nhé



Comments

There are no comments at the moment.