小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。
小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。
第一行两个整数c x(0 < c <= 1000000, 0 <= x <= 100000000)
第二行有c个正整数(每个正整数小于等于100)。
输出一个整数,表示所求的个数。
3 6 2 4 7
4
对于有3个整数构成的数组而言,总共有6个下标连续的区间,他们的和分别为:
2 = 2
4 = 4
7 = 7
2 + 4 = 6
4 + 7 = 11
2 + 4 + 7 = 13
其中有4个和大于等于6,所以答案等于4。
#include <stdio.h> #include <stdlib.h> int n, a[1000005]; long long x; int main() { scanf("%d%lld", &n, &x); long long sum = 0, count = 0; int j = 1; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum += a[i]; while (sum >= x) { count += n - i + 1; sum -= a[j]; j++; } } printf("%lld\n", count); return 0; }