3045.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:3045  User Id:fzk 
Memory:640K  Time:91MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

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( "%d\n", b );
	return 0;
}