← 返回题目列表

Codeforces · 1616/D

D. 保持平均高位

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

给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$ 和一个整数 $$$x$$$。

您需要选择数组中的最大元素数,以便对于每个子段 $$$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 50\,000$$$):数组中整数的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-100\,000 \leq a_i \leq 100\,000$$$)。

第三行包含一个整数 $$$x$$$ ($$$-100\,000 \leq x \leq 100\,000$$$)。

输出

对于每个测试用例,打印一个整数:可以选择的最大元素数。

示例

输入 #1

4
5
1 2 3 4 5
2
10
2 4 2 4 2 4 2 4 2 4
3
3
-10 -5 -10
-8
3
9 9 -3
5

输出 #1

4
8
2
2

注意

在第一个示例中,选择元素的一种有效方法是 $$$[\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}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$$$。

在第三个示例中,一个有效的解决方案是 $$$[\underline{-10}, -5, \underline{-10}]$$$。

在第四个示例中,一个有效的解决方案是 $$$[\underline{9}, \underline{9}, -3]$$$。