CF1582E Pchelyonok and Segments

Pchelyonok 决定送给 Mila 一份礼物。Pchelenok 已经买了一长度为 $n$ 的数组 $a$，但直接送数组太普通了。于是，他决定把数组的若干区间作为礼物送给 Mila！ Pchelenok 希望他的礼物足够美丽，因此他决定选择 $k$ 个互不重叠的数组区间 $[l_1, r_1]$，$[l_2, r_2]$，$\ldots$，$[l_k, r_k]$，使得： - 第一个区间 $[l_1, r_1]$ 的长度为 $k$，第二个区间 $[l_2, r_2]$ 的长度为 $k-1$，……，第 $k$ 个区间 $[l_k, r_k]$ 的长度为 $1$； - 对于每一对 $i < j$，第 $i$ 个区间在数组中出现在第 $j$ 个区间之前（即 $r_i < l_j$）； - 这些区间的区间和严格递增（即设 $sum(l \ldots r) = \sum\limits_{i=l}^{r} a_i$ 表示区间 $[l, r]$ 的和，则 $sum(l_1 \ldots r_1) < sum(l_2 \ldots r_2) < \ldots < sum(l_k \ldots r_k)$）。 Pchelenok 还希望他的礼物尽可能美丽，因此他想知道最大的 $k$ 是多少，使得他能送出这样的礼物！

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的 $2 \cdot t$ 行给出每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出最大的可能的 $k$。

由 ChatGPT 4.1 翻译