4283. [THUPC 2025 Final] 石墨烯

【题目描述】

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$。

【输出格式】

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

【输入样例】

4
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
3 6
1 1 4
5 1 4
4 1
1 2 3 4
4 3 2 1

【输出样例】

1
4
0
2

【样例解释】

为方便表述，下直接用数组 $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$ 个时刻，就能够使得每个区域中都没有正在等位的学生。

【来源】

清华大学学生算法协会 GitLink 仓库