poj3061(尺取法)

时间:2023-03-10 00:38:35
poj3061(尺取法)

---恢复内容开始---

题目意思:给你一段非负序列,再给你一个值k,找出这段序列中最少的连续子序列使得和为k;

解题思路:因为都是正数,我们只需要找到一段区间不大于k,就停止,然后左边趋近看是否能得尽量短的等于k的区间;

代码:

#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
int main()
{
ll n,t,i,j,left,right,s;
ll sum,ans;
ll a[100005];
cin>>t;
while(t--)
{
cin>>n>>s;
for(i=1;i<=n;i++)
cin>>a[i];
left=right=1;
sum=0;ans=n+1;
while(1)
{
while(right<=n&&sum<s)
{
sum+=a[right++];
}
if(sum<s)
break;
ans=min(ans,right-left);
sum-=a[left++];
}
if(ans==n+1)
cout<<"0\n";
else
cout<<ans<<endl;
}
return 0;
}

---恢复内容结束---