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

## binary search

Posted by xiaolonghingis at 2006-11-05 10:36:48 on Problem 3061
In Reply To:Time Limit Error~还能有什么方法可以提高效率 Posted by:zAaron at 2006-11-05 09:10:59
```> //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: