 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
binary searchIn 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:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
