3125.txt

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

Source

Problem Id:3125  User Id:fzk 
Memory:68K  Time:15MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <queue>
using namespace std;

queue<int> q;
int sum[10];

int main( ) {
	int tt, n, i, p, a, t, j;
	scanf( "%d", &tt );
	while( tt-- ) {
		while( !q.empty() )
			q.pop();
		scanf( "%d%d", &n, &p );
		
		for( i=0; i<10; i++ )
			sum[i] = 0;

		for( i=0; i<n; i++ ) {
			scanf( "%d", &a );
			sum[a]++;
			if( p == i )
				a = -a;
			q.push( a );
		}
		i = 0;

		while( 1 ) {
			a = q.front();
			q.pop();
			t = a>0?a:-a;
			
			for( j=t+1; j<10; j++ )
				if( sum[j] )
					break;

			if( j < 10 )
				q.push( a );
			else {
				i++;
				sum[t] --;
				if( a < 0 )
					break;
			}
		}

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