题解：P13049 [GCJ 2020 Qualification] Nesting Depth

· · 题解

题意

题意其实就是插入括号，使得所有括号内的字符串和括号外的字符串都是平衡字符串。

平衡字符串的定义：字符串中每个有出现的字母（题目中是数字）出现的次数都相同。当然，如果出现只一种字母（数字），则它本身就是平衡字符串。

比一般水题加强一点的是位置 p 的嵌套深度是包含 p 的匹配括号对的数量 m。也就是说，这个数字是几，它就要被几个括号嵌套。

题目最重要的一点是，要使得答案字符串长度最短。

思路

好家伙，这不贪心配上字符串，淄博烧烤串吗？

题目让我们维护一个答案字符串：我们先定义一个变量 sd（深度的拼音缩写），再求出第 i 个数字 d。

如果 d>sd 也就是此数字大于当前深度，那就是要加深度了，将答案字符串加左括号，并将 sd 加一。

如果 d<sd 也就是此数字小于当前深度，那就是深度超了，将答案字符串加加右括号，并将 sd 减一。

然后直接将这个数字加入答案字符串，最后可能还有的左括号没有匹配右括号，所以要输出剩下的 sd 个右括号。

最后注意，输出时还要输出测试用例编号。我喜欢将数据总行数递减，所以先将数据总行数存档，后用存档的数据总行数减去现在的数据剩余行数（虽然比较麻烦）。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    int h=t;
    while(t--){
        string r="";
        string s;
        cin>>s;
        int l=s.length();
        int sd=0;
        for(int i=0;i<l;i++){
            int d=s[i]-'0'; 
            while(d>sd){
            r+='(';
            sd++;
            }
            while(d<sd){
            r+=')';
            sd--;
            }
            r+=s[i];
        }
        while(sd>0){
        r+=')';
        sd--;
        }
        cout<<"Case #"<<h-t<<": "<<r<<endl; 
    }
    return 0;
}

细节