题解 | #dd爱框框#

dd爱框框

https://www.nowcoder.com/practice/579c04f8ae0a41cfa9ac49ae1686dd31

用双指针维护当前区间和 ,右指针不断扩展直到 后尽量右移左指针收缩区间,并在每次满足条件时按“长度最短,左指针最小”更新答案;

void solve(){
	int n,x;cin>>n>>x;
    vi a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    int l=1,u=1,v=n,mn=n+1;
    ll s=0;
    for(int i=1;i<=n;++i){
        s+=a[i];
        while(l<=i&&s-a[l]>=x){
            s-=a[l];
            ++l;
        }
        if(s>=x){
            int cur=i-l+1;
            if(cur<mn||(cur==mn&&l<u)){
                mn=cur;
                u=l;
                v=i;
            }
        }
    }
    cout<<u<<" "<<v;
}
全部评论

相关推荐

05-18 12:59
已编辑
东南大学 人工智能
夜晚的精灵:熟悉transformer架构,熟悉机器学习,强化学习这些都可以写上去
点赞 评论 收藏
分享
牛客你可姐:也不要一味的看公司人数决定工作,比如我前司只有30人,但是已经创立了10年……
点赞 评论 收藏
分享
评论
6
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务