3044.txt

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

Problem Id:3044  User Id:fzk 
Memory:232K  Time:0MS
Language:C++  Result:Accepted

Source 

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

int id[50000];
int h[50000];
bool sign[50000];
int temp[2][51000];
int *next = &temp[0][1];
int *pri = &temp[1][1];

bool cmp( int a, int b ) {
	return h[a] > h[b];
}

int main() {
	int n, i, j, count;
	scanf( "%d%*d", &n );
	for( i=0; i<n; i++ ) {
		scanf( "%*d%d", h+i );
		id[i] = i;
		next[i] = i+1;
		pri[i] = i-1;
		sign[i] = true;
	}

	std::sort( id, id+n, cmp );

	count = 0;
	for( i=0; i<n && h[ id[i] ]; i++ ) 
	if( sign[id[i]] ){
		j = id[i];
		count ++;
		if( pri[j] >= 0 && next[j] < n && h[ pri[j] ] == h[ next[j] ] ) {
			sign[ next[j] ] = false;
			next[ pri[j] ] = next[ next[j] ];
			pri[ next[next[j]] ] = pri[j];
		}
		else {
			next[ pri[j] ] = next[j];
			pri[ next[j] ] = pri[j];
		}
	}

	printf( "%d\n", count );
	return 0;
}