#P9711. 数列选数

    ID: 6335 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-补集转化排序贪心交换论证

数列选数

题目描述

给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n 和整数 xx。选出尽可能多的元素,使每个区间 [l,r][l,r](1≤l≤r≤n1\le l\le r\le n)至少满足以下一个条件。

  • l=rl=r。
  • 区间里至少有一个元素未被选择。
  • ∑i=lrai≥(r−l+1)x\sum_{i=l}^{r}a_i\ge(r-l+1)x。

求最多能选多少个元素。

输入格式

第一行是数据组数 TT。每组数据共三行,依次给出整数 nn、nn 个整数 a1,…,ana_1,\ldots,a_n,以及整数 xx。

输出格式

每组数据输出一行,表示最多能选的元素数量。

样例

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
4
8
2
2

第一组可舍弃首项。第二组可舍弃第 3 和第 7 项。第三组可舍弃第 2 项。第四组可舍弃第 3 项。

附加样例 输入 2、输出 2、输入 3、输出 3、输入 4、输出 4。

数据范围

全部数据满足 1≤T≤101\le T\le10,1≤n≤5×1041\le n\le5\times10^4,−105≤ai,x≤105-10^5\le a_i,x\le10^5。

子任务 nn 上限 附加条件 原题所列依赖 分值
1 10 10
2 10210^2 −102≤ai,x≤102-10^2\le a_i,x\le10^2 1 15
3 10310^3 −103≤ai,x≤103-10^3\le a_i,x\le10^3 1、2 20
4 5×1045\times10^4 x=0x=0 15
5 1、2、3、4 40

原 PDF