Subsequence

Subsequence

https://ac.nowcoder.com/acm/problem/107658

题目大意:现有一段长度为10<N<100000的整数序列,每一个整数都小于等于10000。给定一个S<100000000,请你找到一段最小长度的连续子序列,使得子序列的和大于或等于S。
思路:尺取法
1.一个区间看成一个蚯蚓,当子序列的和小于S时,头往前伸,直到子序列的和大于或等于S就停止前伸,记录这个长度。
2.接着把尾部往前伸,同时记录每次的长度,直到子序列的和小于S,尾部不动,开始伸头,继续操作1。
3.在记录的长度中取最小值。
Code:

#include <cstdio>
#include<iostream>
#include <algorithm>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int a[100005];
int main() {
    js; int n,m,t;
    cin>>t;
    while(t--) {
        cin>>n>>m;
        for(int i=1;i<=n;++i) cin>>a[i];
        int ans=n+1,sum=0;
        for(int r=1,l=1;r<=n+1;) {
            if(sum<m) {
                sum+=a[r];
                ++r;
            }
            if(sum>=m) {
                ans=min(ans,r-l);
                sum-=a[l];
                ++l;
                if(l>=r) break;
            }
        }
        if(ans==n+1) cout<<"0\n";
        else
            cout<<ans<<"\n";
    }
    return 0;
}

为雨巨打call

全部评论

相关推荐

吃不饱的肱二头肌很想退休:tnnd 我以为选妹子呢,亏我兴高采烈的冲进来😠
投递快手等公司10个岗位
点赞 评论 收藏
分享
4 收藏 评论
分享
牛客网
牛客企业服务