2013: [USACO 2023 December Contest Gold] Problem 3. Haybale Distribution
题目描述
Farmer John is distributing haybales across the farm!
Farmer John's farm has N (1≤N≤2⋅105) barns, located at integer points x1,…,xN (0≤xi≤106) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤106) and then distribute one shipment to each barn.
Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some ai and bi (1≤ai,bi≤106), ai haybales are wasted per unit of distance left each shipment is transported, and bi haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by
Given Q (1≤Q≤2⋅105) independent queries each consisting of possible values of (ai,bi), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.
输入
The next line contains x1…xN.
The next line contains Q.
The next Q lines each contain two integers ai and bi.
输出
样例输入
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.
SCORING:
- Input 2: N,Q≤10
- Input 3: N,Q≤500
- Inputs 4-6: N,Q≤5000
- Inputs 7-16: No additional constraints.