该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P15260 [USACO26JAN2] Balancing the Barns G

题目描述

农夫约翰有 $N$（$1\le N\le 5\cdot 10^4$）个谷仓沿着一条路排列。第 $i$ 个谷仓包含 $a_i$ 捆干草和 $b_i$ 袋饲料（$0\le a_i,b_i\le 10^9$）。

Bessie 一直在抱怨谷仓之间的不平等。她将农场的 不平衡度 定义为任意谷仓中干草的最大值与任意谷仓中饲料的最小值之差。形式化地，不平衡度为 $\max(a) - \min(b)$。

为了解决 Bessie 的担忧，农夫约翰可以执行恰好 $K$（$1\le K\le 10^{18}$）次转移。在每次转移中，他选择一个谷仓 $i$，卖出它的一捆干草，并为同一个谷仓购买一袋新饲料。注意，他的农场中允许出现负数（他不害怕负债）。形式化地，你需要进行 $K$ 次操作：每次选择一个下标 $i\in [1,N]$，将 $a_i$ 减 $1$，并将 $b_i$ 加 $1$。

帮助农夫约翰确定在执行恰好 $K$ 次转移后可能达到的最小不平衡度。

输入格式

第一行包含 $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)$ 的最小可能值。

输入输出样例 #1

输入 #1

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

输出 #1

-18
90
0
0

说明/提示

在第一个测试用例中，农夫约翰可以从谷仓 $1$ 转移 $10$ 捆干草变成饲料袋。这得到 $a = [-5]$ 和 $b = [13]$。不平衡度为 $\max(a) - \min(b) = -5 - 13 = -18$。

在第二个测试用例中，农夫约翰可以从谷仓 $1$ 转移 $5$ 捆干草，从谷仓 $2$ 转移 $1$ 捆干草。这得到 $a = [95, 95]$ 和 $b = [5, 5]$。不平衡度为 $95 - 5 = 90$。这是农夫约翰可以达到的最小不平衡度。

评分

• 输入 2-4：$K \le 500$，所有测试用例的 $N$ 之和 $\le 500$
• 输入 5-8：所有测试用例的 $N$ 之和 $\le 500$
• 输入 9-13：无额外约束。

翻译由 DeepSeek 完成