| ||||||||||
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