首页 > 代码库 > HDU3351_Seinfeld【栈】

HDU3351_Seinfeld【栈】

2024-07-28 02:51:41   226人阅读

Seinfeld


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1381    Accepted Submission(s): 682

Problem Description
I’m out of stories. For years I’ve been writing stories, some rather silly, just to make simple problems look difficult and complex problems look easy. But, alas, not for this one.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:
1. An empty string is stable.
2. If S is stable, then {S} is also stable.
3. If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.

 

Input

Your program will be tested on one or more data sets. Each data set is described on a single line. The line is a non-empty string of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are of even length.
The last line of the input is made of one or more ’-’ (minus signs.)

Output
For each test case, print the following line:
k. N
Where k is the test case number (starting at one,) and N is the minimum number of operations needed to convert the given string into a balanced one.
Note: There is a blank space before N.
 
Sample Input
}{
{}{}{}
{{{}

---


Sample Output
1. 2
2. 0
3. 1
 
Source

2009 ANARC

题目大意：一串由‘{‘和‘}‘组成的字符串，‘{‘和‘}‘可以互相转换，括号匹配的时候

为稳定状态。输入一个字符串，问最少经过几次变换能达到稳定状态。

思路：先建立一个栈，让每个字符逐个进栈，若相邻的两个字符为"{}"(即相邻括

号匹配)，则两个字符同时出栈。最终栈里边留下括号不匹配的项。

通过观察可知：最终留在栈里的肯定为以下情况

“}}}}…{{{{{…"，即左边全为‘}‘，右边全为‘{‘。那么最少要转换多少次呢。

由题意可知，括号总数为偶数

分别计算‘}‘的个数sum1，‘{‘的个数sum2。

若‘}‘个数为奇数，则‘{‘个数也为奇数，则右括号最少需要变化(sum1+1)/2次，

左括号最少变化(sum2+1)/2次。

比如 }}}}}{{{ 左边至少变化3次才为{}{}{，右边至少变化2次才为}{}

最终为{}{}{}{}。

若‘}‘个数为偶数，则‘{‘个数也为偶数，则右括号最少需要变化sum1/2次，

左括号最少变化sum2/2次。

比如 }}}}}}{{{{ 左边至少变化3次才为{}{}{}，右边至少变化2次才为{}{}

最终为 {}{}{}{}{}。

因为若sum1和sum2都为偶数，则sum1/2 = (sum1+1)/2;

sum2/2 = (sum2+1)/2。

由上可以得到同一个式子：最终sum = (sum1+1)/2 + (sum2+1)/2

#include<stdio.h>
#include<string.h>
char a[2010];
int stack[2010];
int main()
{
    int kase = 1;
    while(~scanf("%s",a) && a[0]!='-')
    {
        int len = strlen(a);
        int top = 1;
        for(int i = 0; i < len; i++)
        {
            if(a[i]=='{')
            {
                stack[top] = 1;
                top++;
            }
            else if(a[i]=='}')
            {
                if(stack[top-1] == 1)
                {
                    stack[top-1] = 0;
                    top--;
                }
                else if(stack[top-1] == 2)
                {
                    stack[top] = 2;
                    top++;
                }
                else
                {
                    stack[top] = 2;
                    top++;
                }
            }
        }
        int sum1,sum2;
        sum1 = sum2 = 0;
        for(int i = 0; i < top; i++)
        {
            if(stack[i] == 2)
                sum2++;
            if(stack[i] == 1)
                sum1++;
        }
        int sum = (sum1+1)/2 + (sum2+1)/2;
        if(top == 1 && stack[0]==0)
            printf("%d. %d\n",kase++,top-1);
        else
            printf("%d. %d\n",kase++,sum);
        memset(a,0,sizeof(a));
    }
    return 0;
}


HDU3351_Seinfeld【栈】


联系
我们