레이팅 미적용농부 존은 길을 따라 배열된 \(N\) (\(1\le N\le 5\cdot 10^4\))개의 축사를 가지고 있다. \(i\)번째 축사에는 건초 더미 \(a_i\)개와 사료 자루 \(b_i\)개가 있다 \((0\le a_i,b_i\le 10^9\)).
베시는 축사 간의 불평등에 대해 불평해 왔다. 베시는 농장의 "불균형"을 어떤 축사의 건초 최대량과 어떤 축사의 사료 최소량의 차이로 정의한다. 형식적으로, 불균형은 \(\max(a) - \min(b)\)이다.
베시의 불만을 해결하기 위해, 농부 존은 정확히 \(K\) (\(1\le K\le 10^{18}\))번의 이전을 수행할 수 있다. 각 이전에서 그는 축사 \(i\)를 선택하여 건초 더미 하나를 팔고, 같은 축사를 위한 새 사료 자루 하나를 산다. 농장의 수량은 음수가 될 수도 있음에 유의하라 (그는 빚을 두려워하지 않는다). 형식적으로, \(K\)번에 걸쳐 인덱스 \(i\in [1,N]\)를 선택하여 \(a_i\)를 1 감소시키고 \(b_i\)를 1 증가시킨다.
정확히 \(K\)번의 이전을 수행한 후 가능한 최소 불균형을 구하도록 농부 존을 도와라.
Problem credits: Rohin Garg
SCORING
- 입력 2-4: \(K\le 500\), 모든 테스트 케이스에 걸친 \(N\)의 합이 \(\le 500\)
- 입력 5-8: 모든 테스트 케이스에 걸친 \(N\)의 합이 \(\le 500\)
- 입력 9-13: 추가 제약 없음.
Problem credits: Rohin Garg
첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1 \leq T \leq 10^3\))가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 줄에 \(a_1\dots a_N\)이 주어진다.
다음 줄에 \(b_1\dots b_N\)이 주어진다.
모든 테스트 케이스에 걸친 \(N\)의 합은 최대 \(5 \cdot 10^4\)이다.
각 테스트 케이스에 대해, \(K\)번의 연산을 수행한 후 가능한 \(\max(a) - \min(b)\)의 최솟값을 하나의 정수로 출력한다.
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