P12056 [THUPC 2025 决赛] 石墨烯

Ecrade_ 看着食堂里来回游走等位的人们陷入了沉思，于是他想到了这样一个问题。 食堂中共有 $n$ 个区域，在食堂即将开门时，第 $i$ 个区域中有 $a_i$ 名正在等位的学生和 $b_i$ 个空位。保证 $\sum\limits_{i=1}^{n}a_i\le \sum\limits_{i=1}^{n}b_i$。 食堂开门后的每个时刻，都会**依次**发生如下两个事件： 1. 每个区域中当前正在等位的学生都会尽可能地坐到该区域的空位上。具体而言，假设第 $i$ 个区域中当前有 $x_i$ 名正在等位的学生和 $y_i$ 个空位。 - 若 $x_i\le y_i$，那么所有正在等位的学生都会坐到空位上，此时第 $i$ 个区域中没有正在等位的学生，且会剩下 $y_i-x_i$ 个空位； - 若 $x_i>y_i$，那么会有恰好 $y_i$ 名正在等位的学生坐到所有空位上，此时第 $i$ 个区域中剩下 $x_i-y_i$ 名正在等位的学生，且没有剩余的空位。 2. 每个区域中当前正在等位的所有学生都会**同时**移动到下一个区域中。具体而言，第 $i$ 个区域中所有正在等位的学生都会移动到第 $(i\bmod n) +1$ 个区域中。 在这群学生中，有恰好 $k$ 名学生因为赶时间上课，在食堂开门的瞬间就打包离开了。而 Ecrade_ 并不清楚这 $k$ 名学生都在哪些区域，所以他想知道，在这 $k$ 名学生所有可能的分布情况中，在食堂开门后，最少经过多少个时刻，就能够使得每个区域中都没有正在等位的学生。

第一行一个整数 $T\ (1\le T\le 5\times 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行两个整数 $n,k\ (1\le n\le 5\times 10^5)$。 - 第二行 $n$ 个整数 $a_1,a_2,...,a_n\ (1\le a_i\le 10^9)$。 - 第三行 $n$ 个整数 $b_1,b_2,...,b_n\ (1\le b_i\le 10^9)$。 保证 $0\le k\le \sum\limits_{i=1}^n a_i\le \sum\limits_{i=1}^{n}b_i$，所有测试数据的 $n$ 的和不超过 $5\times 10^5$。

对于每组测试数据，输出一行一个整数表示答案。

### 样例 #1 解释 为方便表述，下直接用数组 $a,b$ 表示每个时刻后每个区域中正在等位的学生数以及剩余空位数。 对于第一组测试数据，没有学生会离开食堂： - 第一个时刻后，$a=[0,0,0],b=[4,0,0]$。 对于第二组测试数据，没有学生会离开食堂： - 第一个时刻后，$a=[3,0,0,1],b=[3,1,0,0]$； - 第二个时刻后，$a=[1,0,0,0],b=[0,1,0,0]$； - 第三个时刻后，$a=[0,1,0,0],b=[0,1,0,0]$； - 第四个时刻后，$a=[0,0,0,0],b=[0,0,0,0]$。 对于第三组测试数据，所有学生都会离开食堂。 对于第四组测试数据，仅有一名学生会离开食堂： - 若这名学生在第 $1$ 个区域，则 $a$ 会变为 $[0,2,3,4]$： - 第一个时刻后，$a=[3,0,0,1],b=[4,1,0,0]$； - 第二个时刻后，$a=[1,0,0,0],b=[1,1,0,0]$； - 第三个时刻后，$a=[0,0,0,0],b=[0,1,0,0]$。 - 若这名学生在第 $2$ 个区域，则 $a$ 会变为 $[1,1,3,4]$： - 第一个时刻后，$a=[3,0,0,1],b=[3,2,0,0]$； - 第二个时刻后，$a=[1,0,0,0],b=[0,2,0,0]$； - 第三个时刻后，$a=[0,1,0,0],b=[0,2,0,0]$； - 第四个时刻后，$a=[0,0,0,0],b=[0,1,0,0]$。 - 若这名学生在第 $3$ 个区域，则 $a$ 会变为 $[1,2,2,4]$： - 第一个时刻后，$a=[3,0,0,0],b=[3,1,0,0]$； - 第二个时刻后，$a=[0,0,0,0],b=[0,1,0,0]$。 - 若这名学生在第 $4$ 个区域，则 $a$ 会变为 $[1,2,3,3]$： - 第一个时刻后，$a=[2,0,0,1],b=[3,1,0,0]$； - 第二个时刻后，$a=[1,0,0,0],b=[1,1,0,0]$； - 第三个时刻后，$a=[0,0,0,0],b=[0,1,0,0]$。 - 因此，当这名学生在第 $3$ 个区域时，最少经过 $2$ 个时刻，就能够使得每个区域中都没有正在等位的学生。 ### 来源与致谢 来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 。