欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1099. -- A simple problem

1099: A simple problem

时间限制: 1 Sec  内存限制: 64 MB
提交: 190  解决: 44
[提交][状态][讨论版]

题目描述

一个长度为N的数组A, 所有数都是整数 ,0 <= A[i] <= 1000000,1 <= i <= N,1 <= N <= 100000,对于 任意i,j ,1 <=  i  <=  j  <= N,[i, j]中所有数为原数组的一个子区间, 现在要求子区间的和小于等于K的子区间有多少个, 0 <=  K  <= 10000。

虽然xry111很SB,但还是在O(N)的时间复杂度内就做出了这题,你呢?

              

输入

第一行整数T 代表数据组数,1 <= T  <=  12

每组数据第一行 整数 N, K。

接下来一行N个整数,  由空格隔开。

输出

输出子区间的和小于等于K的子区间的个数。 每组输出占一行。

样例输入

1
5  3
1  2  3  4  5

样例输出

4

提示

 我不会告诉你答案可能爆int。


C/C++  long long 请用%lld或者 cout 输出, 不要用%I64d,以及long int

来源

[提交][状态][讨论版]