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?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.
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 ai and bi.
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 Qi
題意：有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歷年真題及參考書，掃碼領?。 竞擦痔峁﹫竺笇Х铡?/strong>
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賬號，即可開始考試
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
