2023-2024年USACO首次月考题目出炉！金级第三题真题及解析

2023-2024赛季的USACO考试已于12月18日正式结束，晋级赛的最新试题也已经公布。近日，USACO官方公布了2023-2024赛季首场月赛的晋级分数线。如果没有晋级，12月可以当做一个练手+熟悉赛制的环节，1、2月的月赛持续发力，USACO可以重复挑战。

今天给大家分享金级试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？

USACO 2023年12月金级第三题

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10⁵) barns, located at integer points x₁,…,x_N (0≤x_i≤10⁶) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10⁶) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some a_i and b_i (1≤a_i,b_i≤106), a_i haybales are wasted per unit of distance left each shipment is transported, and b_i 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 (a_i ,b_i ), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.

INPUT FORMAT (pipe stdin)：

The first line contains N.

The next line contains x1…xN.

The next line contains Q.

The next Q lines each contain two integers a_i and b_i.

OUTPUT FORMAT (pipe stdout)：

Output Q lines, the i th line containing the answer for the ith query.

SAMPLE INPUT：

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

SAMPLE OUTPUT：

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.
Problem credits： Benjamin Q_i

题意：有n个谷仓，给定每个谷仓的位置，现要把所有谷仓的草都运送到一个谷仓y。运送草的代价是y左边的谷仓x的代价是a*(y-x), y右边的谷仓x的代价是b*(x-y)。给q次查询，每次输入a和b的值，求最小的运输总代价。

题解： 

推论：如果一个不是谷仓的位置是最优解，那它左边的一个谷仓也是最优解(左右移动增加和减少的代价相等)。 那就令选取的谷仓为第x个谷仓，先排序，假设当前在第x个谷仓最优，那意味着向左移或者向右移的代价都>=0，向右移，左边就有x个谷仓距离+1，右边有n-x个谷仓距离-1。向右移一格新增的代价就是ax-b(n-x)，向左移一格新增的代价就是b(n+1-x)-a(x-1)。得到两个不等式：

a*x-b*(n-x)>=0

b*(n-x+1)-a*(x-1)>=0

展开：

a*x-b*n+bx>=0

bn-bx+b-ax+a>=0

推出：

bn+b+a >= (a+b)x >= bn

推出：

x >= bn/(a+b)

由上面不等式，计算bn/(a+b)的值x，由于C++除法是向下取整,x和x+1的代价取最小值就是答案。

USACO历年真题及参考书，扫码领取！【Raybet比分 提供报名指导服务】USACO历年真题及参考书

2023-2024年USACO活动时间

第一次月赛：2023年12月15日-18日

第二次月赛：2024年1月26日-29日

第三次月赛：2024年2月16日-19日

美国公开赛：2024年3月15日-18日

（中国学生只能参加到公开赛）

集训营：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷兰）

IOI：2024年9月1日-8日（埃及）

报名方式：参赛者可随时在官网注册账号，注册。报名，只需在活动时间登陆完成答题即可。

官网地址：usaco.org

提交之后，官网会发送一份邮件到您邮箱，邮件中有账号密码

利用已知的账号于密码，登录USACO账号，即可开始考试