题意:有n个正整数组成一个序列。给定整数S,求长度最短的连续序列,使他们的和大于或等于S
思路:题目数据范围10<n<=100000,直接二重循环枚举起点终点复杂度是O(n^2),显然TLE的
sum(i)为前i个数字之和,f(i)代表以第i个数字为结尾的连续子序列长度,要求这个子序列之和大于或等于S而且长度最小。
(1)如果sum(i)<S,那么说明前i个数字加起来都小于S,说明f(i)无解,记为INF
(2)如果sum(i)>=S,那么只需要找到一个最大的j,使得sum(i)-sum(j)>=S即可,那么f(i)=i-j。
注意到j是随i递增而递增的,因此每次j只需要接着上次的位置继续增加就可以了,这样整个题目下来复杂度是O(n)
#include<cstdio> #include<iostream> #define MAXN 100005 #define INF 0x3f3f3f3f using namespace std; int n,S,sum[MAXN],t,T; int solve() { int i,j=0,ans=INF; for(i=1;i<=n;++i) if(sum[i]>=S) { for(;j<i && sum[i]-sum[j]>=S;++j); --j; ans=min(ans,i-j); } return ans==INF? 0:ans; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&S); for(int i=1;i<=n;++i) { scanf("%d",&t); sum[i]=sum[i-1]+t; } printf("%d\n",solve()); } return 0; }