请问一下,D题这么做存在什么问题

//
// Created by good boy on 2024/1/14.
//

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll a[N];
ll n,k,res;

// 找到第一个大于k的位置r
int bsearch(int l,int r){
    while(l<r){
        int mid = (l+r)>>1;
        if(a[r]-a[l-1]>=k)r = mid;
        else l = mid+1;
    }
    return l;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    
    for(int i=1;i<=n;i++){
        res += n-bsearch(i,n);
    }
    cout<<res<<endl;
    return 0;
}

思路就是:拿到数组的前缀和,然后做二分查找,查找到第一个大于k的r的位置,那么不难确定,后面的位置的区间都是符合大于k的范围的

全部评论
全是正数前缀和有单调性,直接lower_bound查找比较好些
点赞 回复 分享
发布于 2024-01-15 10:23 天津

相关推荐

Beeee0927:正确的建议
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务