2751.txt

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

Problem Id:2751  User Id:fzk 
#include "stdio.h"
#include "algorithm"
using namespace std;
struct seg {
	int a, b;
};
seg x[200000];
seg y[200000];
int n, sum, xn, yn;
bool cmp1( seg a, seg b ) {
	return a.a < b.a;
}
bool cmp2( seg a, seg b ) {
	return a.b > b.b;
}
bool init( ) {
	int i, j, k;	
	seg t;
	scanf( "%d", &n );
	if( n == 0 )
		return false;
	sum = 0;	
	for( i=0, j=0, k=0; i<n; i++ ) {
		scanf( "%d%d", &t.a, &t.b );
		sum += t.b;
		if( t.a > t.b )
			y[ k++ ] = t;
		else
			x[ j++ ] = t;
	}
	xn = j;
	yn = k;
	if( xn )
		sort( x, x+xn, cmp1 );
	if( yn )
		sort( y, y+yn, cmp2 );

	return true;
}
bool judge( int ans ) {
	int i;
	for( i=0; i<xn; i++ ) {
		if( ans < x[i].a )
			return false;
		ans += x[i].b - x[i].a;
	}
	for( i=0; i<yn; i++ ) {
		if( ans < y[i].a )
			return false;
		ans += y[i].b - y[i].a;
	}
	return true;
}
int main( ) {
	int a, b, c;
	while( init( ) ) {
		a = -1;
		b = 2000000;
		while( b > a+1 ) {
			c = ( a + b ) / 2;
			if( judge( c ) )
				b = c;
			else
				a = c;
		}
		printf( "%d\n", sum+b );
	}

	return 0;
}