Balancing the Barns
플래티넘 III의견: 0
Farmer John has \(N\) (\(1\le N\le 5\cdot 10^4\)) barns arranged along a road. The
\(i\)-th barn contains \(a_i\) bales of hay and \(b_i\) bags of feed
\((0\le a_i,b_i\le 10^9\)).
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\le K\le 10^{18}\)) 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\in [1,N]\), decrement \(a_i\), and increment
\(b_i\).
Help Farmer John determine the minimum possible imbalance after performing
exactly \(K\) transfers.
Problem credits: Rohin Garg
SCORING
- Inputs 2-4: \(K\le 500\), sum of \(N\) over all testcases is \(\le 500\)
- Inputs 5-8: Sum of \(N\) over all testcases is \(\le 500\)
- Inputs 9-13: No additional constraints.
Problem credits: Rohin Garg
The first line contains \(T\) (\(1 \leq T \leq 10^3\)), the number of independent
test cases.
The first line of each test case contains \(N\) and \(K\).
The following line contains \(a_1\dots a_N\).
The following line contains \(b_1\dots b_N\).
The sum of \(N\) over all test cases is at most \(5 \cdot 10^4\).
For each test case, output a single integer, the minimum possible value of
\(\max(a) - \min(b)\) after performing \(K\) operations.
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-18
90
0
0In 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.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Gold
평가 및 의견
Balancing the Barns
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Balancing the Barns