Poj Solution 3045

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

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

struct cow {
    int sum, w, s;
}c[50000];

int n;

bool cmp( cow a, cow b ) {
    return a.sum < b.sum;
};

bool check( int k ) {
    int sum = 0, i;
    for( i=0; i<n; i++ ) {
        if( c[i].sum - sum > k )
            return false;
        sum += c[i].w;
    }
    return true;
}

int main() {
    int i, sum = 0, a, b, cc;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%d%d", &c[i].w, &c[i].s );
        sum += c[i].w;
    }

    for( i=0; i<n; i++ )
        c[i].sum = sum - c[i].w - c[i].s;

    std::sort( c, c+n, cmp );

    a = -500000000; b = 500000000;
    while( a < b-1 ) {
        cc = (a+b)/2;
        if( check( cc ) )
            b = cc;
        else 
            a = cc;
    }
    printf( "%dn", b );
    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 *