问题 1099. -- A simple problem

1099: A simple problem

时间限制:1000 ms 内存限制:64 MB
提交:232 解决:70
[ 提交][ 状态][ 讨论版]

题目描述

一个长度为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

来源

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