题解 | #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;
}
全部评论

相关推荐

04-13 11:19
门头沟学院 HTML5
NullPointe...:27实习的都快结束了吧
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

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