3145.txt

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

Source

Problem Id:3145  User Id:fzk 
Memory:976K  Time:8390MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;

typedef pair<int,int> p_i;
p_i p[100], q[100];

set< p_i > s;

p_i ans[900];

int main( ) {
	int n, i, k, count = 1, j;
	p_i p, b;
	set< p_i >::iterator iter;
	char w[2];
	while( scanf( "%d", &n ) == 1 && n ) {
		s.clear( );
		
		for( i=1; i<900; i++ )
			ans[i].first = -1;
		
		printf( "Case %d:\n", count++ );
		j = 0;
		while( n-- ) {
			scanf( "%1s%d", w, &k );

			if( w[0] == 'B' ) {
				j--;
				for( i=1; i<900; i++ )
					if( ans[i].first < 0 || k%i <= ans[i].first%i )
						ans[i].first = k, ans[i].second = j;
				s.insert( make_pair( k, j ) );
				
				continue;
			}

			if( s.empty() )
				printf( "-1\n" );
			else if( k < 900 )
				printf( "%d\n", -ans[k].second );
			else {
				b.first = k-1;
				b.second = 1000000;
				p.first = 0;
				p.second = -100000;
				while( true ) {
					iter = s.lower_bound( p );
					if( iter == s.end() )
						break;
					if( iter->first%k < b.first%k || iter->first%k == b.first%k && iter->second < b.second )
						b = *iter;
					p.first = (iter->first/k+1)*k;
				}
				printf( "%d\n", -b.second );
			}
		}
		printf( "\n" );
	}
	return 0;
}