CF1616D Keep the Average High

给定一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $x$。 你需要从数组中选择尽可能多的元素，使得对于数组中的任意一个长度大于 $1$ 的连续子段 $a_l, a_{l+1}, \ldots, a_r$（$l < r$），满足以下两个条件之一： - 该子段中至少有一个元素未被选择，或者 - $a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量。 接下来是 $t$ 组测试数据，每组测试数据包含三行。 第一行包含一个整数 $n$（$1 \leq n \leq 50000$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-100000 \leq a_i \leq 100000$）。 第三行包含一个整数 $x$（$-100000 \leq x \leq 100000$）。

对于每个测试用例，输出一个整数，表示你最多可以选择的元素个数。

在第一个样例中，一种合法的选择方式是 $[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$。所有子段都满足至少一个条件。例如，对于子段 $l=1, r=2$，元素 $2$ 未被选择，满足第一个条件。对于子段 $l=3, r=5$，有 $3+4+5=12 \ge 2 \cdot 3$，满足第二个条件。 不能选择所有元素，因为对于 $l=1, r=2$，所有元素都被选择，且 $a_1 + a_2 = 3 < 2 \cdot 2$。因此，最多可以选择 $4$ 个元素。 在第二个样例中，一种合法的选择方式是 $[\underline{2}, \underline{4}, 2, \underline{4}, 2, \underline{4}, 2, \underline{4}, 2, \underline{4}]$。 在第三个样例中，一种合法的选择方式是 $[\underline{-10}, -5, \underline{-10}]$。 在第四个样例中，一种合法的选择方式是 $[\underline{9}, \underline{9}, -3]$。 由 ChatGPT 4.1 翻译