Poj Solution 2566

http://poj.org/problem?id=2566

#include"stdio.h"
#include"algorithm"
#include"math.h"
using namespace std;
int sum[100010];
int *id[100010];
const bool cmp( int *a, int *b )
{
    return *a<*b;
}
int main()
{
    int n,m,i,t,j,a,b,ans,temp,k;
    while( 1 )
    {
        scanf( "%d %d", &n, &m );
        if( n == 0 && m == 0 ) break;        
        sum[0] = 0;
        id[0] = sum;
        for( i=1; i<=n; i++ )
        {
            scanf( "%d", &sum[i] );
            
            id[i] = sum + i;
            sum[i] += sum[i-1];
        }
        n++;
        sort( id, id+n, cmp );
        for( k=0; k<m; k++ )
        {
            scanf( "%d", &t );
            ans = 2000000000;
            for( i=0,j=1; i<n; i++ )
            {
                if( i >= j ) j++;
                if( j >= n ) break;
                while( j<n-1 && *id[j]-*id[i] < t )
                    j++;
                if( ( temp = abs( *id[j] - *id[i] - t ) ) < ans )
                    a = i, b = j, ans = temp;
                if( j-1 > i && ( temp = abs( *id[j-1] - *id[i] - t ) ) < ans )
                    a = i, b = j-1, ans = temp;
            }
            if( id[a] > id[b] )swap( a, b );
            printf( "%d %d %dn", abs( *id[a] - *id[b] ), id[a]-sum+1, id[b]-sum );
        }
    }
    return 0;             

}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *