原题地址
题意:找到最多的大于K的连续子序列的个数
思路:前缀和+枚举,想说的都在代码里
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include<iostream>
using namespace std;
#define ll long long
int cmd(int a ,int b){
return abs(a)>abs(b);
}
ll arr[1000000]={0};
ll brr[1000000]={0};
ll crr[1000000]={0};
int main() {
ll n , k;
cin >>n>>k;
ll cnt=0;
ll sum=0;
for(int i=1;i<=n;i++)
cin >>arr[i];
for(int i=1;i<=n;i++)
brr[i] = brr[i-1]+arr[i];
int l=0,r=0;
//下面枚举的方法是从第一个开始找,找到第R个合适的数,然后再从第二个数开始找到第二个数相对应合适的数
//我的疑惑,有没有可能会出现第二个数到合适的数之间的个数,比第一个数到合适的数之间的个数小。
//回答:不可能,因为再多一个数的情况下,都没找到合适的数,在少一个数的情况下,个数比前者少是不会发生的
while(r<=n){//前缀和不超过n
if(brr[r]-brr[l]<k){//是判断前r-l个和是否大于k
r++;//表明前r-l个和小于k,r需要后移
continue;
}
cnt+=(n-r)+1;
//如果前r-l个和大于k的话,意味着剩下n-r个数都满足大于k,加+1是因为当前前缀和也是满足的
l++;//此时已经算完了前r个了,应该判断前r-l个和
}
//因为第一遍已经把1->r个数判断完毕,所以第二个数及其以后数就不用考虑它前面的数了
cout<<cnt<<endl;
return 0;
}