Chạy vòng tròn

Lời giải: Chạy vòng tròn

Hướng tiếp cận

Với mỗi cặp bò $(i,j)$ có $s_i>s_j$, số lần vượt = $\lfloor L(s_i-s_j)/s_{max}\rfloor$ (trong đó $s_{max}$ là tốc độ bò nhanh nhất). Tính tổng này hiệu quả bằng tiền tố lap + đếm nghịch chuyển.

Nhận xét quan trọng

1. Cuộc đua kết thúc tại thời điểm $T=LC/s_{max}$. Bò $i$ vượt bò $j$ mỗi $C/(s_i-s_j)$ giây, nên số lần vượt = $\lfloor T(s_i-s_j)/C\rfloor =\lfloor L(s_i-s_j)/s_{max}\rfloor$.
2. Đặt $\text{lap}[k]=\lfloor L{s}_k/s_{max}\rfloor$, $\text{frac}[k]=L{s}_{k}mod{s}_{max}$.
3. $\lfloor L(s_i-s_j)/s_{max}\rfloor =(\text{lap}[i]-\text{lap}[j])-[\text{frac}[i]<\text{frac}[j]]$.
4. Tổng ${\sum }_{i>j}(\text{lap}[i]-\text{lap}[j])$ dùng tiền tố. Số cặp $\text{frac}[i]<\text{frac}[j]$ với $i>j$ = đếm nghịch chuyển của mảng frac.

Thuật toán

1. Sắp xếp tốc độ tăng dần. Tính lap[], frac[].
2. Tính ${\sum }_{i>j}(\text{lap}[i]-\text{lap}[j])$ bằng tiền tố lap.
3. Đếm nghịch chuyển của frac[] dùng BIT (Fenwick Tree).
4. Đáp án = bước 2 - bước 3.

Độ phức tạp

• Thời gian: $O(N\log N)$
• Bộ nhớ: $O(N)$