#PU1355. USACO 2023 December Contest, Gold — Problem 3. Haybale Distribution

    ID: 1291 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec23来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2023 December Contest, Gold — Problem 3. Haybale Distribution

USACO 2023 December Contest, Gold — Problem 3. Haybale Distribution

题目描述

Farmer John is distributing haybales across the farm! Farmer John's farm has NN (1≤N≤2⋅105)(1\le N\le 2\cdot 10^5) barns, located at integer points x1,…,xNx_1,\dots, x_N (0≤xi≤106)(0 \le x_i \le 10^6) on the number line. Farmer John's plan is to first have NN shipments of haybales delivered to some integer point yy (0≤y≤106)(0 \le y \le 10^6) and then distribute one shipment to each barn. Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some aia_i and bib_i (1≤ai,bi≤106)(1\le a_i, b_i\le 10^6), aia_i haybales are wasted per unit of distance left each shipment is transported, and bib_i haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point yy to a barn at point xx, the number of haybales wasted is given by

$$\begin{cases} a_i\cdot (y-x) & \text{if } y \ge x \\ b_i\cdot (x-y) & \text{if } x > y \end{cases}.$$

Given QQ (1≤Q≤2⋅105)(1\le Q\le 2\cdot 10^5) independent queries each consisting of possible values of (ai,bi)(a_i,b_i), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses yy optimally.

输入格式

The first line contains NN. The next line contains x1…xNx_1\dots x_N. The next line contains QQ. The next QQ lines each contain two integers aia_i and bib_i.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
1 4 2 3 10
4
1 1
2 1
1 2
1 4
11
13
18
30
For example, to answer the second query, it is optimal to select $y=2$. Then the
number of wasted haybales is equal to
$2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=1+0+1+2+8=13$.