C市现在要转移一批罪犯到D市,C市有n名罪犯,按照入狱时间有顺序,另外每个罪犯有一个罪行值,值越大罪越重。现在为了方便管理,市长决定转移入狱时间连续的c名犯人,同时要求转移犯人的罪行值之和不超过t,问有多少种选择的方式?
输入描述:
第一行数据三个整数:n,t,c(1≤n≤2e5,0≤t≤1e9,1≤c≤n),第二行按入狱时间给出每个犯人的罪行值ai(0≤ai≤1e9)
输出描述:
一行输出答案。
输入例子:
3 100 2
1 2 3
输出例子:
2
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
long n = 0;
long t = 0;
long c = 0;
long a[200000];
scanf("%ld%ld%ld",&n,&t,&c);
for(long i = 0;i<n;i++)
{
scanf("%ld",&a[i]);
}
long count = 0;
bool flag = false;
long sum = 0;
for(long i = 0;i<=n-c;i++)
{
if(!flag)
{
for(long j = i;j<c+i;j++)
{
sum +=a[j];
}
flag = true;
}else
{
sum = sum+a[c+i-1]-a[i-1];
}
if(sum <= t)
count++;
}
printf("%ld",count);
return 0;
}