题目详情题解（0）讨论（0）提交记录（0）

CF2089B1.Canteen (Easy Version)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的简单版本。两个版本的区别在于此版本中，$$k=0$$。只有当你解决了该问题的所有版本时才能进行 hack。

Ecrade 有两个由整数构成的序列 $$a0,a1,…,an−1a_0, a_1, \ldots, a_{n - 1}$$ 和 $$b0,b1,…,bn−1b_0, b_1, \ldots, b_{n - 1}$$。保证 $$aa$$ 中所有元素的总和不超过 $$bb$$ 中所有元素的总和。

初始时，Ecrade 可以对序列 $$aa$$ 进行恰好 $$kk$$ 次修改。保证 $$kk$$ 不超过 $$aa$$ 的总和。每次修改操作如下：

  • 选择一个整数 $$ii$$（$$0 \le i < n$$）满足 $$a_i>0a\_i > 0$$，并执行 $$ai:=ai−1a_i := a_i - 1$$。

然后，Ecrade 将对 $$aa$$ 和 $$bb$$ 依次执行以下三个操作，这三个操作构成一轮操作：

  1. 对每个 $$0≤i<n0 \le i < n$$：$$t := \min(a_i, b_i)$$，$$a_i := a_i - t$$，$$b_i := b_i - t$$；
  2. 对每个 $$0≤i<n0 \le i < n$$：$$c_i := a_{(i - 1) \bmod n}$$；
  3. 对每个 $$0≤i<n0 \le i < n$$：$$a_i := c_i$$。

Ecrade 想知道，在对 $$aa$$ 进行恰好 $$kk$$ 次修改后，使得 $$aa$$ 中所有元素变为 $$00$$ 所需的最小轮数。

然而，这似乎有些复杂，因此请帮助他！

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $$tt$$（$$1 \le t \le 2 \cdot 10^4$$）。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $$nn$$、$$k$$（$$1 \le n \le 2 \cdot 10^5$$，$$k = 0$$）。

每个测试用例的第二行包含 $$nn$$ 个整数 $$a_0,a_1,…,a_n−1a\_0, a\_1, \ldots, a\_{n - 1}$$（$$1 \le a_i \le 10^9$$）。

每个测试用例的第三行包含 $$nn$$ 个整数 $$b_0,b_1,…,b_n−1b\_0, b\_1, \ldots, b\_{n - 1}$$（$$1 \le b_i \le 10^9$$）。

保证所有测试用例的 $$nn$$ 之和不超过 $$2⋅1052 \cdot 10^5$$。同时保证每个测试用例中 $$aa$$ 的总和不超过 $$bb$$ 的总和，且 $$kk$$ 不超过 $$aa$$ 的总和。

输出格式

对于每个测试用例，输出在对 $$aa$$ 进行恰好 $$kk$$ 次修改后，使得 $$aa$$ 中所有元素变为 $$0$$ 所需的最小轮数。

输入输出样例

  • 输入#1

    4
3 0
1 1 4
5 1 4
4 0
1 2 3 4
4 3 2 1
4 0
2 1 1 2
1 2 2 1
8 0
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

    输出#1

    1
4
4
8

说明/提示

在此版本中，Ecrade 不能对 $$aa$$ 进行修改。

在第一个测试用例中：

  • 第一轮操作后，$$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]$$。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页