Haybale Distribution

题目描述

农夫约翰正在把干草捆分发到整个农场！ 农夫约翰的农场有 $N$ 个 $(1\le N\le 2\cdot 10^5)$ 谷仓，位于数轴上的整数点 $x_1,\dots, x_N$ $(0 \le x_i \le 10^6)$。农夫约翰的计划是先将 $N$ 批干草捆运送到某个整数点 $y$ $(0 \le y \le 10^6)$，然后将每一批运到各个谷仓（每个谷仓一批）。 不幸的是，农夫约翰的运输服务非常浪费。具体而言，对于某个 $a_i$ 和 $b_i$ $(1\le a_i, b_i\le 10^6)$，当每批运输向左移动时，每单位距离会浪费 $a_i$ 个干草捆；当每批运输向右移动时，每单位距离会浪费 $b_i$ 个干草捆。形式化地，对于一批从点 $y$ 运到位于点 $x$ 的谷仓，其浪费的干草捆数量为

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

给定 $Q$ 个 $(1\le Q\le 2\cdot 10^5)$ 相互独立的询问，每个询问给出可能的 $(a_i,b_i)$ 取值，请你帮助农夫约翰确定：如果他最优地选择 $y$，最少会浪费多少干草捆。

输入格式

第一行包含 $N$。 第二行包含 $x_1\dots x_N$。 第三行包含 $Q$。 接下来 $Q$ 行每行包含两个整数 $a_i$ 和 $b_i$。

输出格式

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

5
1 4 2 3 10
4
1 1
2 1
1 2
1 4

11
13
18
30

提示

例如，为了回答第二个询问，最优选择 $y=2$。此时浪费的干草捆数量为 $2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=1+0+1+2+8=13$。 SCORING: Input 2: $N,Q\le 10$ Input 3: $N,Q\le 500$ Inputs 4-6: $N,Q\le 5000$ Inputs 7-16: No additional constraints. Problem credits: Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold