XidianOJ 1099 A simple problem

题目描述

一个长度为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的子区间的个数。每组输出占一行。

--正文

明明是简单的题，却做了半天。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

long long a[];

int n,k,i,j;

int main(){

    int time,T; scanf("%d",&T);

    for (time=;time<=T;time++){

        int now = ;

        LL sum = ,res = ;

        scanf("%d %d",&n,&k);

        for (i=;i<=n;i++){

            scanf("%lld",&a[i]);

            sum += a[i];

            if (sum <= k) {

                res += i - now + ;

            }

            else {

                while (sum > k){

                    sum = sum - a[now]; now ++;

                }

                res += i - now + ;

            }

        }

        printf("%lld\n",res);

    }

    return ;

}

巴特西

XidianOJ 1099 A simple problem

题目描述

输入

输出

最新文章

热门文章