鄭輕OJ 1396: 愚人節的禮物

1396: 愚人節的禮物

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 975  Solved: 365

Submit Status Web Board

Description

 四月一日快到了，Vayko想了個愚人的好辦法——送禮物。嘿嘿，不要想的太好，這禮物可沒那麼簡單，Vayko為了愚人，準備了一堆盒子，其中有一個盒子裡面裝了禮物。盒子裡面可以再放零個或者多個盒子。假設放禮物的盒子裡不再放其他盒子。

    用()表示一個盒子，B表示禮物，Vayko想讓你幫她算出愚人指數，即最少需要拆多少個盒子才能拿到禮物。

Input

首先輸入一個整數T（0<T<=20），表示有T組測試執行個體。

    每組測試包含一個長度不大于1000,隻包含“(”,“)”和“B”三種字元的字元串，代表Vayko設計的禮物透視圖。

    你可以假設，每個透視圖畫的都是合法的。

Output

    對于每組測試，請在一行裡面輸出愚人指數。

Sample Input

2((()((B)()))())(B)      

Sample Output

41      

HINT

Source32

輕院2013級新生賽

思路：做到右至 B 周遊‘（’當有‘）’的時候可算打開一個箱子；右到左也一樣，取最小值

代碼：

。

#include<stdio.h>
#include<string.h>
#define G 11030
#include<algorithm>

using namespace std;

int main() {
	char wqs[G-10000];
	int T,ans1,ans2,ans,B_wz;
	scanf("%d",&T);
	while(T--) {
		ans=ans1=ans2=0;
		scanf("%s",wqs);
		for(int j=0; j<strlen(wqs); j++)
			if(wqs[j]=='B') {
				B_wz=j;
				break;
			}
		for(int j=0; j<B_wz; j++) {
			if(wqs[j]=='(')
				ans1++;
			if(wqs[j]==')')
				ans1--;
		}
		for(int j=strlen(wqs); j>B_wz; j--) {
			if(wqs[j]=='(')
				ans2--;
			if(wqs[j]==')')
				ans2++;
		}
		ans=(ans1>ans2? ans2:ans1);
		printf("%d\n",ans);
	}
	return 0;
}