Poj Solution 2456

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

#include <stdio.h>
#include <algorithm>
using namespace std;

int pos[100000], n, cc;

bool check( int l )
{
    int i, r, j;
    for( r=cc-1,i=0,j=1; j<n && r; j++ )
    {
        if( pos[j]-pos[i]>=l )
        {
            r--;
            i=j;
        }
    }
    return r == 0;
}

int main()
{
    int i, j, a, b, c;
    scanf( "%d %d", &n, &cc );

    for( i=0; i<n; i++ )
    scanf( "%d", &pos[i] );

    sort( pos, pos+n );    

    a = 0, b = ( pos[n-1] - pos[0] ) / ( cc - 1 ) + 1;
    
    while( b > a+1 )
    {
        c = ( a + b ) / 2;
        if( check(c) ) a = c;
        else b = c;
    }
    printf( "%dn", a );

    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 *