3190.txt

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

Source

Problem Id:3190  User Id:fzk 
Memory:1532K  Time:154MS
Language:C++  Result:Accepted

Source 

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

using namespace std;

int empty[50000];
int use[50000];
int a[50000], b[50000];

typedef pair<int,int> p_i;
p_i p[100000];

int main( ) {
	int i, n, m, ans=0;
	scanf( "%d", &n );
	for( i=0; i<n; i++ ) {
		scanf( "%d%d", a+i, b+i );
		p[i*2].first = a[i];
		p[i*2].second = (1<<16) | i;
		p[i*2+1].first = b[i]+1;
		p[i*2+1].second = i;
	}

	sort( p, p+2*n );
	m = 0;

	for( i=0; i<2*n; i++ ) {
		if( p[i].second < (1<<16) )
			empty[m++] = use[ p[i].second ];
		else {
			if( m == 0 )
				use[ p[i].second - (1<<16) ] = ++ans;
			else
				use[ p[i].second - (1<<16) ] = empty[--m];
		}
	}

	printf( "%d\n", ans );
	for( i=0; i<n; i++ )
		printf( "%d\n", use[i] );

	return 0;
}