学步园

模拟题,两种队列来标记右括号,P队列是第i个右括号左边有几个左括号,W队列是第i个右括号与它的左括号直接有几对括号,包括本身.

用一个数组来模拟这个括号队列,不难发现,第a[i]个右括号的位置是i+a[i],即它左边的左括号加右括号数.

先将数组清0,再将右括号标1,然后依次对每个右括号进行查找,看它与它配对的左括号直接有几个1(包括本身)就可以了..

每个右括号配对的左括号就是往左数的第一个0,对用过的左括号标2.

#include <cstdio>
#include <string.h>
using namespace std;
int main(){
	int nCase;
	int ar[21];
	int kh[45];
	scanf("%d",&nCase);
	while(nCase--){
		int n;
		memset(ar,0,sizeof(ar));
		memset(kh,0,sizeof(kh));
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&ar[i]);
			kh[ar[i]+i]=1; //该右括号位置标1 
		}
		for(int i=0;i<n;i++){
			int r=ar[i]+i;
			int res=0;
			for(int j=r;j>=0;j--){
				if(kh[j]==1)res++;//右括号的个数 
				if(kh[j]==0){//未使用的括号 
					printf("%d",res);
					if(i!=n-1)printf(" "); 
					kh[j]=2;//标记为左括号 
					break;//找到退出 
				}
			}
		} 
		printf("\n");
	}
	return 0;
}