AtCoder Beginner Contest 167 F:Bracket Sequencing 贪心分析

首先我们知道,判一个字符串是否合法,肯定是判任意前缀 ( 的个数一定大于等于 ) 的个数 而多个字符串考虑什么样的字符串放在最左边比较好。 对于一个字符串对拼接有影响的括号一定是自己内部匹配后剩的括号,比如 )(()( 内部匹配一对,剩2个左括号,一个右括号。 显然字符串内部括号匹配完后,剩的都是“(”,且剩的左括号的最多,这样的字符串放在最左边。比如()()(( 剩2个左括号 同理,最右边一定是,剩的右括号最多的字符串。 依照最左最右,我们往中间放。 首先左括号剩的多的肯定尽量放左边,右括号剩的多的尽量放右边。 然后考虑次左应该放什么最优。 先把左括号剩的多的在左边安排好: 由于最左边