3179.txt

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

Source

Problem Id:3179  User Id:fzk 
Memory:4092K  Time:561MS
Language:C++  Result:Accepted

Source 

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

int sum[1024][1024],s;

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

void init( )
{
	int i,j;
	
	for(i=1;i<=s;i++)
	for(j=1;j<=s;j++)
		sum[i][j]=0;
}

void set( int x, int y )
{
	int j;
	
	x++,y++;

	while(x<=s)
	{
		for(j=y;j<=s;j+=lowbit(j))
		{
			sum[x][j]++;
		}
		x+=lowbit(x);
	}
}

int count(int x,int y)
{
	int ans=0,j;
	
	while(x>0)
	{
		for(j=y;j>0;j-=lowbit(j))
		{
			ans+=sum[x][j];
		}
		x-=lowbit(x);
	}

	return ans;
}


int query( int l, int b, int r, int t )
{

	l++,b++,r++,t++;

	return count(r,t)-count(r,b-1)-count(l-1,t)+count(l-1,b-1);
}

int f[1001];
int x[500], y[500];
int t[1001], n;

bool check( int len, int c ) {
	int i, j, ti, tj;

	if( len < 0 )
		return false;

	for( i=0; i<2*n; i++ )
		t[i] = std::upper_bound( f, f+2*n+1, f[i]+len ) - f - 1;

	ti = -1;
	for( i=0; i<2*n; i++ ) {
		if( t[i] == ti )
			continue;
		
		ti = t[i];

		if( query( i, 0, ti, 2*n-1 ) >= c ) {
			tj = -1;

			for( j=0; j<2*n; j++ ) {
				if( tj == t[j] )
					continue;

				tj = t[j];

				if( query( i, j, ti, tj ) >= c )
					return true;
			}
		}
	}
	return false;
}

int main( ) {
	int i, c, a, b, ans;

	scanf( "%d%d", &c, &n );

	for( i=0; i<n; i++ ) {
		scanf( "%d%d", x+i, y+i );
		f[i*2] = x[i];
		f[i*2+1] = y[i];
	}
	
	s = 2*n;

	std::sort( f, f+2*n );

	f[2*n] = 20000000;

	init( );

	for( i=0; i<n; i++ ) {
		a = std::lower_bound( f, f+2*n, x[i] ) - f;
		b = std::lower_bound( f, f+2*n, y[i] ) - f;
		set( a, b );
	}

	a = -1; b = f[2*n-1] - f[0];

	while( a < b-1 ) {
		ans = (a+b)/2;
		if( check( ans, c ) )
			b = ans;
		else
			a = ans;
	}

	printf( "%d\n", b+1 );
	
	return 0;
}