1 条题解

  • 1

    这道题虽然能用滑动窗口,但二分+前缀和也不是不能写。

    遍历前缀和数组,对于sumisum_i,找到第一个大于等于target+sumitarget+sum_i的位置,减去ii,就是子数组长度,然后打擂台。

    由于输入的都是正数,前缀和数组必定有序,所以可以用二分。

    #include<bits/stdc++.h>
    using namespace std;
    int num[100005],tar,sum[100005],n;
    int ans=INT_MAX;
    int main(){
    	cin>>n>>tar;
    	for(int i=1;i<=n;i++){
    		cin>>num[i];
    		sum[i]=sum[i-1]+num[i];
    	}
    	int ttar;
    	for(int i=1;i<=n;i++){
    		ttar=tar+sum[i];
    		int ind=lower_bound(sum+1,sum+1+n,ttar)-sum;
    		if(sum[ind]>=ttar)	ans=min(ans,ind-i);
    	}
    	if(ans==INT_MAX)	cout<<0;
    	else	cout<<ans;
    }
    

    点个赞再走吧^^。

    • 1

    信息

    ID
    910
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    59
    已通过
    18
    上传者