题目大意:现有一段长度为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; }