| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题不是水题么 79ms水过,为什么马甲总是比主号时间少?附说明维护两个指针
这里有个性质证明一下,其实显而易见的
性质一:如果a[2]+a[3]>=S的话a[1]+a[2]+a[3]也大于S,且长度大于前者(明显是废话)
性质二:如果a[2]+a[3]>=S的话a[2]+a[3]+a[4]也大于S,且长度大于前者(明显也是废话)
但是用这两个性质可以把时间降到O(N)
如果你a[i]+a[i+1]+...a[i+k]>=S,那么在判断长度之前先使用性质一缩长度。while(sum>=s){sum-=a[head++];}
然后根据性质二我们可以直接使用这个head指针做下一个循环,也就是说,下一次增大尾指针的时候保证sum<S,不然根据性质二,我们必然多求一个大于最小值的值
所以说整个循环只有尾指针不断增大,不需要回朔,复杂度O(N)
用这方法TLE你来找我
贴个代码
#include <stdio.h>
#define MAX 100100
int main()
{
int T,N,S;
int i=0,data[100100],min,head=0,rear=0,sum=0;
scanf("%d",&T);
while(T--)
{
min=MAX;
scanf("%d %d",&N,&S);
for(i=0;i<N;++i)
{
scanf("%d",data+i);
}
head=0;
rear=1;
sum=data[0];
while(rear<N)
{
while(rear <N && sum<S)
{
sum+=data[rear++];
}
sum-=data[head++];
while(sum>=S)
{
sum-=data[head++];
}
if (sum+data[head-1]>=S && rear-head+1<min)
{
min=rear-head+1;
}
}
if(MAX == min)
{
puts("0");
}
else
{
printf("%d\n",min);
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator