Cửa Hàng Tối Ưu
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên trục số có $N$ cửa hàng tại các vị trí $x_1, x_2, \ldots, x_N$ (đã sắp xếp tăng dần). Mỗi cửa hàng có trọng số (số lượng khách hàng) $w_i$. Cần chọn một vị trí (số nguyên) để đặt kho hàng sao cho tổng khoảng cách có trọng số $\sum_{i=1}^{N} w_i \cdot |pos - x_i|$ là nhỏ nhất.
In ra tổng khoảng cách có trọng số nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^5)$.
- $N$ dòng tiếp theo, mỗi dòng chứa $x_i$ và $w_i$ $(|x_i| \le 10^9, 1 \le w_i \le 10^9)$.
Dữ liệu ra
- In ra tổng khoảng cách có trọng số nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 1 1 2 1 3 1 |
2 |
| 3 1 1 3 2 5 1 |
6 |
Giới hạn
- $1 \le N \le 10^5$
- $|x_i| \le 10^9$
- $1 \le w_i \le 10^9$
Community Discussion