TRZ_2007 的博客

TRZ_2007 的博客

题解 AT2586 【Insertion】

posted on 2019-06-14 20:46:33 | under 题解 |

Remarks

发布翻译的来水一篇题解……
本蒟蒻相信,我的那篇翻译一定能让人看得懂
所以还是水一篇题解来加深大佬们的思考。

Solution

这道题目实际有几个难点,看看样例三知道了。首先我们来分析一下怎么过掉前2个样例。先给出这两个样例。

#1

Input.txt
3
())

Output.txt
(())

#2

Input.txt
6
)))())

Output.txt
(((()))())

首先我们来看看#1,输入就是3个字符,让你补全。我们很容易看出,这个字符串需要你补一个(,可是怎么来实现呢?

其实很简单,我们只需要一个变量 $cut$ 来判断是否匹配,我们定义 $cut$ 的运算:碰上(加一;碰上)减一。则,如果 $cut$ 为正数,说明我们少了 $cut$ 个),若 $cut$ 为负数,则我们少了 $cut$ 个(

这部分的代码

for(int i=1;i<=n;i++)
{
    if (str[i] == '(') cut++;
    if (str[i] == ')') cut--;
}

难道这样就好了吗?

出题人:你想多了。

来看看第三个样例

#3

Input.txt
8
))))((((

Output.txt
(((())))(((())))

如果你还用我们上面提到的解法,那就会出错!因为)(数量相等!

怎么办呢?

也简单,我们只需要……
注意,正解来了!!

我们只需要再定义一个 $cut2$ ,定义如果有出现)(多的状况, $cut2$ 就加一,接下来 $cut$ 就归0,以免重复计算。

$code$

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

char str[N];
int cut1,cut2,n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>str[i];
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='(') cut1++;
        if(str[i]==')')
        {
            cut1--;
            if(cut1<0) cut2++,cut1 = 0;
        }
    }
    for(int i=1;i<=cut2;i++)
        cout<<"(";
    for(int i=1;i<=n;i++)
        cout<<str[i];
    for(int i=1;i<=cut1;i++)
        cout<<")";
    cout<<"\n";
}

望审核通过……
$Line$ :99