← 返回题目列表

Codeforces · 2159/D1

D1. 逆最小分区(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在此版本中,仅要求您查找$$$f(a)$$$。只有解决了该问题的所有版本,您才能破解。

对于$$$k$$$正整数的某些序列$$$b$$$,该序列的成本定义如下$$$^{\text{*}}$$$:

$$\mathtt{成本}(b)=\left\lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}}\right\rceil$$

假设您将序列 $$$c$$$ 划分为一个或多个序列,以便这些序列在连接时变为 $$$c$$$。例如,当序列 $$$c$$$ 为 $$$[3,1,4,1,5]$$$ 时,对序列进行分区的一些有效方法为 $$$[[3,1],[4,1,5]]$$$、$$$[[3],[1,4,1],[5]]$$$、$$$[[3,1,4,1,5]]$$$。另一方面, $$$[[3,1],[1,5]]$$$ 和 $$$[[3,4,1],[1,5]]$$$ 不是划分序列的有效方法。

对于正整数序列 $$$c$$$ 的分区,分区的总成本定义为分区中每个序列的成本之和。然后,我们将 $$$f(c)$$$ 定义为划分序列 $$$c$$$ 的最小总成本。

给定一个包含 $$$n$$$ 正整数的序列 $$$a$$$,您必须计算 $$$f(a)$$$ 的值。

$$$^{\text{*}}$$$给定一个实值$$$x$$$,$$$\left\lceil{x}\right\rceil$$$被定义为不小于$$$x$$$的最小整数。例如,$$$\left\lceil{3.14}\right\rceil$$$ 的值为 $$$4$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{18}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$4\cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出问题的答案。

示例

输入
复制

4
5
3 1 4 1 5
10
9 2 6 5 3 5 8 9 7 9
8
1 2 3 4 5 6 7 8
2
1 1000000000000000000

输出
复制

2
4
5
2

注意

对于第一个测试用例,分区 $$$[[3,1,4,1],[5]]$$$ 给出的总成本为 $$$1+1=2$$$。

对于第二个测试用例,分区 $$$[[9,2,6,5,3],[5,8,9,7,9]]$$$ 给出的总成本为 $$$2+2=4$$$。

对于第三个测试用例,分区 $$$[[1],[2,3,4],[5,6,7,8]]$$$ 给出的总成本为 $$$1+2+2=5$$$。

对于第四个测试用例,分区 $$$[[1],[1\,000\,000\,000\,000\,000\,000]]$$$ 给出的总成本为 $$$1+1=2$$$。