Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题不是水题么 79ms水过,为什么马甲总是比主号时间少?附说明

Posted by Belldandy at 2013-12-02 22:11:20 on Problem 3061
维护两个指针
这里有个性质证明一下,其实显而易见的
性质一:如果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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator