Hướng dẫn giải của Chạy vòng tròn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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 = $⌊ L (s_{i} - s_{j}) / s_{m a x} ⌋$ (trong đó $s_{m a x}$ 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

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

Thuật toán

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

Độ phức tạp

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

Bình luận

Không có bình luận tại thời điểm này.