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
查看17道真题和解析