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

O(n)复杂度。

Posted by memoryyang at 2010-08-08 15:59:03 on Problem 2018
#include <cstdio>
int i, j, n, k, s[100002], a;
int main()
{
	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &j);
		s[i] = s[i-1] + j;
	}
	for (i = 0, j = 0; i <= n-k; i++)
	{
		if ((i-j)*(s[i+k]-s[j]) - (i+k-j)*(s[i]-s[j]) > 0) j = i;
		a >?= 1000*(s[i+k]-s[j])/(i+k-j);
	}
	printf("%d\n", a);
	return 0;
}

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