Trạm Thu Phí Vượt Ngưỡng Long Thành

Mô tả

Cao tốc Long Thành – Dầu Giây có một tuyến trạm thu phí dọc theo đường đi. Mỗi trạm ghi nhận doanh thu trong một ngày (tính theo đơn vị nghìn đồng). Ban quản lý đường cao tốc muốn biết: có bao nhiêu cặp trạm khác nhau mà tổng doanh thu của hai trạm trong cặp vượt qua một ngưỡng an toàn tài chính K (nghìn đồng). Một cặp trạm được tính theo vị trí khác nhau trên tuyến, và cặp (i, j) được coi như (j, i). Bạn cần đếm số lượng cặp như vậy.

Đầu vào

• Một mảng số nguyên revenue đại diện cho doanh thu của từng trạm theo thứ tự dọc tuyến.
• Một số nguyên K là ngưỡng doanh thu cần vượt qua.

Đầu ra

• Trả về một số nguyên là số lượng cặp trạm khác nhau có tổng doanh thu lớn hơn K.

Ràng buộc

• 1 <= n <= 10^5, trong đó n là số lượng trạm (độ dài mảng revenue).
• -10^6 <= revenue[i] <= 10^6 với mọi i.
• -10^9 <= K <= 10^9.

Ví dụ

Ví dụ 1:

• Đầu vào: revenue = [3, 1, 4, 2, 5], K = 5
• Đầu ra: 7
• Giải thích: Sắp xếp mảng được [1, 2, 3, 4, 5]. Các cặp có tổng lớn hơn 5 là: (1,5)=6, (2,4)=6, (2,5)=7, (3,4)=7, (3,5)=8, (4,5)=9. Cặp (1,4)=5 không thỏa vì cần lớn hơn. Tổng cộng có 6 cặp. Kiểm tra lại bằng hai con trỏ: left=0, right=4 ta có 1+5>5, đếm 4 cặp; left=0, right=3 ta có 1+4 không lớn hơn 5, tăng left; left=1, right=3 ta có 2+4>5, đếm 2 cặp; left=1, right=2 ta có 2+3 không lớn hơn 5, tăng left. Tổng cộng 6 cặp thỏa mãn.