Editorial for Sòng bạc

Với mỗi chỉ số $j$ ~j~ $(1 \le j \le m)$ ~(1 \le j \le m)~, ta tiến hành tính tổng độ chênh lệch giữa tất cả các cặp người chơi đối với con số thứ $j$ ~j~.

Tiến hành sắp xếp giá trị các con số thứ $j$ ~j~ của $n$ ~n~ người theo thứ tự tăng dần. Duyệt qua với mỗi chỉ số $i$ ~i~ $(1 \le i \le n)$ ~(1 \le i \le n)~, ta tính tổng độ chênh lệch giữa phần tử thứ $i$ ~i~ với các phần tử nhỏ hơn (đứng trước phần tử $i$ ~i~ do đã sắp xếp). Có thể sử dụng Tổng tiền tố (Prefix Sum) để tính toán trong $O(n)$ ~O(n)~.

Độ phức tạp: $O(n.m)$ ~O(n.m)~.

Editorial for Sòng bạc

Sòng bạc

Comments