一、题目内容
POJ 3061 原题地址
二、题意解释
从给定序列里找出区间和大于等于S的最小区间的长度。
三、代码及注释
#include<cstdio>
#include<algorithm>
using namespace std
;
int cn
,n
,S
;
int a
[1000005];
int sum
[1000005];
void solve(){
int s
=0,t
=0,sum
=0;
int res
=n
+1;
while(true){
while(t
<n
&&sum
<S
){
sum
+=a
[t
++];
}
if(sum
<S
) break;
res
=min(res
,t
-s
);
sum
-=a
[s
++];
}
if(res
==n
+1){
printf("0\n");
}else{
printf("%d\n",res
);
}
}
int main(){
scanf("%d",&cn
);
while(cn
--){
scanf("%d%d",&n
,&S
);
for(int i
=0;i
<n
;i
++){
scanf("%d",&a
[i
]);
}
solve();
}
return 0;
}
