2765.txt

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

Problem Id:2765  User Id:fzk 
Memory:148K  Time:31MS
Language:C++  Result:Accepted

Source 

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

struct product{
	char w[100];
	char name[110][100];
	int per[110];
	int most[110], least[110];
	int m;
}p[10];

int n;

void clac( product &a ) {
	int s = 0, r = 100, i, j, k, low[100], up[100], sum, sh, rh;

	for( i=a.m-1; i>=0; i-- ) {
		if( a.per[i] != -1 ) {
			s = a.per[i];		// be sure that per[i] >= s;
			a.most[i] = a.least[i] = a.per[i];
		}
		else if( s < 1 )
			s = 1;

		low[i] = s;
		r -= s;
	}

	s = 100;
	sum = 0;
	for( i=0; i<a.m; i++ ) {
		if( a.per[i] != -1 ) {
			s = a.per[i];		// be sure that per[i] <= s;
		}
		up[i] = s;
		sum += up[i] - low[i];
	}

	for( i=0; i<a.m; i++ ) 
	if( a.per[i] == -1 ){
		a.most[i] = low[i];
		a.least[i] = up[i];

		for( j=low[i]; j<=up[i]; j++ ) {
			sh = sum;
			rh = r;
			
			for( k=i; k<a.m && j < up[k]; k++ )
				sh -= up[k] - j;
			for( k=i; k>=0 && j > low[k]; k-- ) {
				sh -= j - low[k];
				rh -= j - low[k];
			}

			if( rh >= 0 && rh <= sh ) {
				if( a.least[i] > j )
					a.least[i] = j;
				if( a.most[i] < j )
					a.most[i] = j;
			}
		}//for
	}//if

}

int get_most( product &a, char *w ) {
	int i;
	for( i=0; i<a.m; i++ )
		if( strcmp( a.name[i], w ) == 0 )
			return a.most[i];
	return 0;
}

int get_least( product &a, char *w ) {
	int i;
	for( i=0; i<a.m; i++ )
		if( strcmp( a.name[i], w ) == 0 )
			return a.least[i];
	return 0;
}
void query_most( char *w ) {
	int i, l = -1, t;
	bool key = false;
	for( i=0; i<n; i++ ) {
		t = get_least( p[i], w );
		if( t > l )
			l = t;
	}

	for( i=0; i<n; i++ )
		if( get_most( p[i], w ) >= l ) {
			if( key ) printf( " " );
			printf( "%s", p[i].w );
			key = true;
		}
	printf( "\n" );
}
		
void query_least( char *w ) {
	int i, l = 200, t;
	bool key = false;
	for( i=0; i<n; i++ ) {
		t = get_most( p[i], w );
		if( t < l )
			l = t;
	}

	for( i=0; i<n; i++ )
		if( get_least( p[i], w ) <= l ) {
			if( key ) printf( " " );
			printf( "%s", p[i].w );
			key = true;
		}
	printf( "\n" );
}

bool input( ) {
	int i, j;
	char c;
	scanf( "%d", &n );
	if( n <= 0 )
		return false;

	for( i=0; i<n; i++ ) {
		scanf( "%s", p[i].w );
		scanf( "%d", &p[i].m );
		for( j=0; j<p[i].m; j++ ) {
			scanf( "%s", p[i].name[j] );
			c = getchar();
			if( c != '\n' )
				scanf( "%d%%", &p[i].per[j] );
			else
				p[i].per[j] = -1;
		}
	}

	for( i=0; i<n; i++ )
		clac( p[i] );
	return true;
}

int main( ) {
	int t;
	char w1[100], w2[100];
	while( input( ) ) {
		scanf( "%d", & t );
		while( t-- ) {
			scanf( "%s %s", w1, w2 );
			if( w1[0] == 'm' )
				query_most( w2 );
			else
				query_least( w2 );
		}
	}

	return 0;
}