题目分析

题意简述

本题定义了一种被称作“数字洋葱（$DO$）”的由括号构成的结构，给出了其递归定义、权重计算规则以及价格排序规则。对于给定的一个 $DO$，需要找出比它价格更贵且不存在价格介于二者之间的下一个 $DO$（即 $Next More Expensive DO，NMED$）。

输入

• 包含 $T$ 个测试用例，$T$ 的值在输入文件首行给出。
• 每个测试用例的 DO 写在单独一行，行末用 “$” 表示输入结束，$“(”、“)”$ 和 “ ”之间至少有一个空格。
• 输入 $DO$ 的最小权重为 $1$，最大权重为 $30$。

输出

每个测试用例输出一行，包含对应的 $NMED 并以 “ ” 结尾，“(”、“)” 和 “ ”$ 之间至少有一个空格。

解题思路

递归处理 DO 结构

依据 $DO$ 的递归定义，把 $DO$ 拆分成内部（$A$）和外部（$B$）两部分进行处理。

判断最后一个 DO

借助 isLast 函数判断一个 $DO$ 是否为当前权重下的最后一个 $DO$。若为最后一个，意味着要对其结构进行调整以得到下一个更贵的 $DO$。

寻找 B 的起始位置

利用 findBPos 函数找出 $DO$ 中外部部分 $B$ 的起始位置，从而把 $DO$ 拆分成内部和外部两部分。

生成连续括号序列

通过 kuohao 函数生成指定数量的连续 “()” 序列。

计算下一个更贵的 DO

依据不同情形递归计算下一个更贵的 $DO$：

1. 若外部部分 $B$ 不是最后一个 $DO$，那么下一个更贵的 $DO$ 是当前内部部分加上外部部分的下一个更贵的 $DO$。
2. 若外部部分 $B$ 是最后一个 $DO$，而内部部分 $A$ 不是最后一个 $DO$，那么下一个更贵的 $DO$ 是内部部分的下一个更贵的 $DO$ 加上与外部部分括号数量相同的连续 “()” 序列。
3. 若外部部分 $B$ 是最后一个 $DO$，内部部分 $A$ 也是最后一个 $DO$ 且外部部分有括号，那么下一个更贵的 $DO$ 是比内部部分多一层括号的连续 “()” 序列加上比外部部分少一层括号的连续 “()” 序列。
4. 若外部部分 $B$ 是最后一个 $DO$，内部部分$A$ 也是最后一个 $DO$ 且外部部分无括号，那么下一个更贵的 $DO$ 是比当前 $DO$ 多一层括号的连续 “()” 序列。

代码实现

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

void print(string s){
    int len = s.length();
    for(int i = 0; i < len; i++) printf("%c ", s[i]);
    printf("$\n");
}

bool isLast(string s){
    int len = s.length();
    for(int i = 0; i < len/2; i++){
        if(s[i] == ')') return 0;
    }
    return 1;
}

int findBPos(string s){
    int kh = 1, len = s.length();
    for(int i = 1; i < len; i++){
        if(s[i] == '(') kh++;
        else{
            kh--;
            if(kh == 0) return i+1;
        }
    }
    return len;
}

string kuohao(int n){
    string s = "";
    for(int i = 0; i < n; i++) s += "()";
    return s;
}

string next(string s){
    if(!s.length()) return "()";
    int bpos = findBPos(s);
    string B = s.substr(bpos), khA = s.substr(0, bpos);
    string A = khA.substr(1, khA.length()-2);
    if(!isLast(B)){
        return khA + next(B);
    }
    else if(!isLast(A)){
        return "(" + next(A) + ")" + kuohao((B.length()/2));
    }
    else if(B.length()){
        return "(" + kuohao(A.length()/2+1) + ")" + kuohao(B.length()/2-1);
    }
    else{
        return kuohao(s.length()/2+1);
    }
}

int main() {
    int T;
    cin >> T;
    for(int i = 0; i < T; i++){
        char c;
        char str[80] = {'\0'};
        int len = 0;
        while(1){
            cin >> c;
            if(c == '$') break;
            str[len] = c;
            len++;
        }
        string DO(str);
        print(next(DO));
    }
    return 0;
}    

代码说明

1. 输入处理

   • 借助 cin 读取测试用例的数量 $T$。
   • 针对每个测试用例，通过循环读取字符，直至遇到 “$” 为止，把读取的字符存入字符数组 str，之后转换为 string 类型的 DO。

2. 输出处理

   • print 函数会把 string 类型的 DO 逐字符输出，字符间用空格分隔，最后输出 “$” 并换行。

3. 核心函数

   • isLast 函数：判断一个 $DO$ 是否为当前权重下的最后一个 $DO$。
   • findBPos 函数：找出 $DO$ 中外部部分 $B$ 的起始位置。
   • kuohao 函数：生成指定数量的连续 “()” 序列。
   • next 函数：递归计算下一个更贵的 $DO$。

4. 主函数逻辑

   • 读取测试用例数量 $T$。
   • 对每个测试用例，读取输入的 $DO$，调用 next 函数计算下一个更贵的 $DO$，再用 print 函数输出结果。