题目描述
给定一个长度为 n 的序列 a1,a2,…,an 和整数 x。选出尽可能多的元素,使每个区间 [l,r](1≤l≤r≤n)至少满足以下一个条件。
- l=r。
- 区间里至少有一个元素未被选择。
- ∑i=lrai≥(r−l+1)x。
求最多能选多少个元素。
输入格式
第一行是数据组数 T。每组数据共三行,依次给出整数 n、n 个整数 a1,…,an,以及整数 x。
输出格式
每组数据输出一行,表示最多能选的元素数量。
样例
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≤10,1≤n≤5×104,−105≤ai,x≤105。
| 子任务 |
n 上限 |
附加条件 |
原题所列依赖 |
分值 |
| 1 |
10 |
|
10 |
| 2 |
102 |
−102≤ai,x≤102 |
1 |
15 |
| 3 |
103 |
−103≤ai,x≤103 |
1、2 |
20 |
| 4 |
5×104 |
x=0 |
|
15 |
| 5 |
|
1、2、3、4 |
40 |
原 PDF