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 woshiliyiyiyiyi at 2012-06-17 21:23:22 on Problem 3671
#include<stdio.h>

#define Max 30010

int main()
{
	int a[Max];
	int i;
	int n;
	int j;
	int k;
	int length;
	int sum;

	fscanf(stdin, "%d", &n);
	length = n; sum = 0;
	i = 0; j = 0;
	while(n--)
	{
		fscanf(stdin, "%d", &k);
		if (k == 1)
		{
			j++;
		}
		else
		{
			sum += j;
			a[i++] = j;
			j = 0;
		}
	}

	k = sum + j;
	sum = 0;
	for (j=0; j<i; j++)
	{
		if (a[j] + i - j + sum > k)
		{
			k = a[j] + i - j + sum; 
		}
		sum += a[j];
	}
	
	printf("%d", length - k);

	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