不是VIP会员,不能显示答案

题目解答

题目:
(尺取法求区间个数)给n个非负整数a[1]a[2],...,a[n],求区间和小于或等于k的区间个数,即求使SUM= a[L]+a[L+1]+...+a[R-1]+a[R]<=k的区间[L,R]的个数(1≤L≤R≤n),但由于对内存和复杂度有要求,本题已经用尺取法写好部分代码,请补全程序。

输入第一行两个整数 n,k(1 ≤ n ≤ 1000000, 0 ≤ n ≤ 1000000000000000)。

第二行为n个数,表示a[1]~a[n]的值(0≤a[i]≤1000000000)。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int mx=1e6+10;

int n,a[mx];

ll k,sum,ans;

int main()

{

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

for (int i=1; i<=n; ++i)

{

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

}

int r=0;

for (int i=1; i<=n; ++i)

{

while (r<n)

{

if (___(1)___) ___(2)___;

else break;

}

___(3)___;

if (i<=r) ___(4)___;

else ___(5)___;

}

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

}


选择题

1) ①处应填( )

2) ②处应填( )

3) ③处应填( )

4) ④处应填( )

5) ⑤处应填( )
考点:
分析:
解答:
评论:
老师: