1 条题解
-
0
Guest
-
1
这道题虽然能用滑动窗口,但二分+前缀和也不是不能写。
遍历前缀和数组,对于,找到第一个大于等于的位置,减去,就是子数组长度,然后打擂台。
由于输入的都是正数,前缀和数组必定有序,所以可以用二分。
#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
- 上传者