1727.txt

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

#include "stdio.h"
#include "algorithm"

struct event{
	int t, x;
}p[100000];

bool cmp( event &a, event &b ) {
	return a.x+a.t < b.x+b.t;
}
int n, m;

void input( ) {
	int i;
	scanf( "%d%d", &n, &m);
	for( i=0; i<n; i++ )
		scanf( "%d%d", &p[i].t, &p[i].x );

}

bool check( int lt ) {
	int i, lx, j;
	lx = -100000000;
	for( i=0, j=0; i<n&&j<=m; i++ ) {
		if( abs( p[i].x - lx ) > p[i].t - lt ) {
			lx = p[i].x + ( p[i].t - lt );
			j++;
		}
	}
	return j<=m;
}

int main( ) {
	int i, s, a, b, j, c;
	scanf( "%d", &s );
	for( i=1; i<=s; i++ ) {
		input( );
		a = 1000000;
		b = -10000000;

		for( j=0; j<n; j++ )
			if( a > p[j].t ) a = p[j].t;

		std::sort( p, p+n, cmp );
		a++;
		while( a > b+1 ) {
			c = (a+b)/2;
			if( check( c ) )
				b = c;
			else
				a = c;
		}

		printf( "Case %d: %d\n", i, b );
	}
	return 0;
}