参考做法(Python)

Pop_Slime 发表于 3年前 · 关联问题 一鸣师姐与括号序列

from functools import * # `True` if `a` is placed on the left def cmp(a, b): if (a[1] >= 0) != (b[1] >= 0): # If `a` and `b` shift the depth in different directions, return a[1] >= 0 # the one increasing the depth should be placed on the left else: if a[1] >= 0: return a[2] >= b[2] # If they both increase the depth, the one demanding less depth goes left else: return (a[2] - a[1]) < (b[2] - b[1]) # If they both decrease the depth, the one with less left brackets goes right # Receive input n = int(input()) sl = [input() for i in range(n)] # Raw input data dl = [] # Computed item list for i in range(len(sl)): s = sl[i] d = 0 e = 0 for c in s: # Compute `d`, how many levels of depth does this item in-/de-creases if c == '(': d += 1 else: d -= 1 # Compute `e`, how many levels of depth does this item actually demands (negated) if d < e: e = d dl.append((i, d, e)) # Also record the original index as the items are sorted later dl.sort(key=cmp_to_key(lambda a, b: -1 if cmp(a, b) else 1)) try: depth = 0 # Check if the depth ever goes negative throughout the items for sel in dl: if depth + sel[2] < 0: raise RuntimeError("NO") depth += sel[1] # Check if the final depth is 0, i.e. all the left brackets are closed if depth != 0: raise RuntimeError("NO") print("YES") print(' '.join([str(i[0] + 1) for i in dl])) except RuntimeError as ex: print(ex.args[0])