Phân Phối Cỏ Khô

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John cần phân phối cỏ khô cho $N$ chuồng bò nằm tại các vị trí $x_{1}, x_{2}, \dots, x_{N}$ trên trục số. Ông giao $N$ kiện cỏ đến một điểm tập kết $y$ , rồi phân phối mỗi kiện đến một chuồng.

Chi phí vận chuyển kiện cỏ từ điểm $y$ đến chuồng tại vị trí $x$ là:

$a \cdot (y - x)$ nếu $y \geq x$
$b \cdot (x - y)$ nếu $x > y$

Với $Q$ truy vấn, mỗi truy vấn cho một cặp $(a, b)$ , hãy tìm tổng chi phí tối thiểu khi chọn $y$ tối ưu.

Lưu ý: Mỗi kiện cỏ được giao đến đúng một chuồng, mỗi chuồng nhận đúng một kiện. Tất cả các kiện trong cùng một truy vấn có cùng hệ số $(a, b)$ .

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ).
Dòng $2$ : $N$ số nguyên $x_{1}, \dots, x_{N}$ ( $0 \leq x_{i} \leq 10^{6}$ ).
Dòng $3$ : Số nguyên $Q$ ( $1 \leq Q \leq 2 \cdot 10^{5}$ ).
$Q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a$ và $b$ ( $1 \leq a, b \leq 10^{6}$ ).

Dữ liệu ra

In ra $Q$ dòng, mỗi dòng là tổng chi phí tối thiểu cho truy vấn tương ứng.

Ràng buộc

Test $2$ : $N, Q \leq 10$ .
Test $3$ : $N, Q \leq 500$ .
Các test $4$ - $6$ : $N, Q \leq 5000$ .
Các test $7$ - $16$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
5 1 4 2 3 10 4 1 1 2 1 1 2 1 4	11 13 18 30	Với $(a, b) = (1, 1)$ : tối ưu đặt điểm tập kết tại $y = 3$ , chi phí = $1 \cdot 2 + 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 1 \cdot 7 = 11$ .

Bình luận

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