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

Time Limit Error~还能有什么方法可以提高效率

Posted by zAaron at 2006-11-05 09:10:59 on Problem 3061 
//poj3036.cpp
//Problem A:Subsequence 
/*Algorithm:
	1. the length of subsequence from 1 to n
	2. length = S / average 
*/
#include <iostream>
using namespace std;
int v[100000];
int nums,N,S;

void Input(int nums)
{
 
	for(int i=0; i<nums; i++)
		cin >> v[i];
}

int Average()
{
	int sum = 0;
	for (int i=0; i<N; i++)
		sum += v[i];
	const average = sum / N;  
	return average;
}

bool Solve(const int length)
{
	int sum = 0; // sum of nums of length
	for (int i=0; i<length; i++)
		sum += v[i];
	for (i=0; i<N-length+1; i++)
	{
		if (sum >= S) return true;
		sum += v[i+length] - v[i];
	}
	return false;
}

int main()
{	
	cin >> nums;
	while(nums--)
	{
		cin >> N >> S;
		Input(N);
		/* minimal_length */
		int minimal_length  = S / Average();
		if ( Solve(minimal_length) == true )
		while(1) 
		{
			minimal_length--;  
			if ( Solve(minimal_length) == false ) {minimal_length++; break; }
		}
		else if ( Solve(minimal_length) == false )
		while(1) 
		{
			minimal_length++;  
			if ( Solve(minimal_length) == true) break;
		}
		/* minimal_length */
		cout << minimal_length << endl;
	}
	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