2026 年 USACO竞赛 第二场比赛金奖组问题一—Balancing the Barns

Farmer John has N (1≤N≤5⋅104) barns arranged along a road. The i-th barn contains ai bales of hay and bi bags of feed (0≤ai ,bi ≤109).

Bessie has been complaining about the inequality between barns. She defines the "imbalance" of the farm as the difference between the maximum hay in any barn and the minimum feed in any barn. Formally, the imbalance is max(a)−min(b).

To address Bessie's concerns, Farmer John can perform exactly K (1≤K≤1018 ) transfers. In each transfer, he selects a barn i, sells one of its haybales, and buys it a new bag of feed for the same barn. Note that there can be negative amounts in his farm (he is not afraid of debt). Formally, K times, you choose an index i∈[1,N], decrement ai, and increment bi .

Help Farmer John determine the minimum possible imbalance after performing exactly K transfers.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤103), the number of independent test cases.

The first line of each test case contains Nand K.

The following line contains a1…aN.

The following line contains b1…bN.

The sum of N over all test cases is at most 5⋅104 .

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a single integer, the minimum possible value of max(a−min(b) after performing K operations.

SAMPLE INPUT:

4
1 10
5
3
2 6
100 96
0 4
3 3
1 1 2
0 0 1
3 3
1 2 2
0 1 1

SAMPLE OUTPUT:

-18
90
0
0

In the first test case, Farmer John can transfer 10 haybales from barn 1 into bags of feed. This leaves a=[−5] and b=[13]. The imbalance is max(a−min(b)=−5−13=−18.

In the second test case, Farmer john can transfer 5 haybales from barn 1 and 1 haybale from barn 2. This leaves a=[95,95] and b=[5,5]. The imbalance is 95−5=90. This is the minimum imbalance Farmer John can achieve.

SCORING:

Inputs 2-4: K≤500, sum of N over all testcases is ≤500
Inputs 5-8: Sum of N over all testcases is ≤500
Inputs 9-13: No additional constraints.

Problem credits: Rohin Garg

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询