P13144 [GCJ 2018 #1C] Ant Stack

Scott 有一个蚂蚁农场，里面有 $N$ 只蚂蚁。每只蚂蚁都有一定的体长和体重。 今天，Scott 给蚂蚁们设置了一个挑战：他把一些食物放在蚂蚁农场的顶部。蚂蚁们会尝试通过把自己叠成一根竖直的“蚂蚁塔”来够到食物，每只蚂蚁都直接背着下一只蚂蚁。这样，每只蚂蚁都要承受其上方所有蚂蚁的重量。Scott 的蚂蚁们非常强壮，每只蚂蚁最多可以承受自身重量的 6 倍。例如，一只重 8 毫克的蚂蚁可以承受两只各重 24 毫克的蚂蚁！每只蚂蚁也有一个体长；具体长度不重要，只要它们的长度都不相同即可。 - 蚂蚁塔必须是线性的。除了最顶上的蚂蚁外，每只蚂蚁正上方必须有且只有一只蚂蚁；除了最底下的蚂蚁外，每只蚂蚁正下方必须有且只有一只蚂蚁。 - 蚂蚁塔中蚂蚁的体长必须从下到上严格递减；这保证了每只新加入蚂蚁都能顺利爬到顶部。 - 对于塔中的每只蚂蚁，其上方所有蚂蚁的总重量不得超过该蚂蚁自身重量的 6 倍。 请问最多能有多少只蚂蚁组成这样一根蚂蚁塔？

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为一个整数 $N$，表示蚂蚁的数量。第二行为 $N$ 个整数 $W_1, W_2, ..., W_N$，其中 $W_i$ 表示第 $i$ 只蚂蚁的重量（单位：毫克）。蚂蚁按照体长严格递增的顺序给出。注意，实际长度值未给出，只需关心顺序。

对于每组测试数据，输出一行 `Case #x: y`，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示最多能组成的蚂蚁塔的蚂蚁数量。

**样例解释** 在样例 1 中，有两只蚂蚁。第一只重 9 毫克，第二只重 1 毫克，且第二只比第一只体长更长。第一只蚂蚁足够强壮，可以承受第二只蚂蚁（因为它能承受 $9 \times 6$ 毫克），但由于第二只蚂蚁体长更长，不能叠在第一只上。第二只蚂蚁无法承受第一只蚂蚁（因为它只能承受 $1 \times 6$ 毫克，小于 9 毫克）。所以只能单独选其中一只蚂蚁组成“蚂蚁塔”。 在样例 2 中，三只蚂蚁可以全部组成一根蚂蚁塔，第三只承受第二只，第二只承受第一只。 在样例 3 中，最优解是第九只蚂蚁在最底下，其上方再叠七只其它蚂蚁。 **数据范围** - $7 \leqslant T \leqslant 100$。 **测试点 1（16 分，可见）** - 恰有 6 组数据 $N = 100$；其余 $T-6$ 组 $2 \leqslant N \leqslant 50$。 - $1 \leqslant W_i \leqslant 1000$，对所有 $i$。 **测试点 2（27 分，隐藏）** - 恰有 6 组数据 $N = 10^5$；其余 $T-6$ 组 $2 \leqslant N \leqslant 500$。 - $1 \leqslant W_i \leqslant 10^9$，对所有 $i$。 由 ChatGPT 4.1 翻译