题解2：SP5449 ANARC09A - Seinfeld

思路：

考虑贪心。

1. 统计未配对的 {：

   • 当遇到一个 { 时，增加未配对的 { 数量。
   • 当遇到一个 } 时，有两种情况：
     • 如果有多余的 {，那么就用这个 } 与之前的 { 配对。
     • 如果没有多余的 {，增加 \(1\) 次。

2. 遍历结束后：

   • 当我们遍历完字符串后，可能还会剩下一些未配对的 {，需要通过将一部分 { 替换为 } 来完成配对。需要的操作次数是 \(\frac{wt}{2}\)，其中 \(wt\) 是剩余未配对的 { 的数量。

代码：

#include<bits/stdc++.h>
using namespace std;
char s[2001];
int main(){
	for(int cs=1;;cs++){
		scanf("%s",s);
		if(s[0]=='-')return 0;
		int cnt=0;
		int wt=0;
		for(char*p=s;*p;p++){
			if(*p=='{'){
				wt++;
			}else{
				if(wt==0){
					wt=1;
					cnt++;
				}else{
					wt--;
				}
			}
		}
		printf("%d. %d\n",cs,cnt+wt/2);
	}
}