Processing math: 100%

YZOJ P3384 [校内训练20171201]括号替换问题

YZOJ P3384 [校内训练20171201]括号替换问题

时间限制:1000MS      内存限制:262144KB

难度:5.0

  • 问题描述

这里有一个关于合法的括号序列的问题。如果插入“+” 和 “1” 到一个括号序列,我们能得到一个正确的数学表达式,我们就认为这个括号序列是合法的。例如,序列 “(())()”, “()” 和 “(()(()))” 是合法的,但是 “)(“, “(()” 和 “(()))(” 是不合法的。我们有一个仅由 “(”,“)” 和 “?” 组成的括号序列,你必须将 “?” 替换成括号,从而得到一个合法的括号序列。

对于给定仅由 “(”,“)” 和 “?” 组成的括号序列,你需要将 “?” 替换成括号,得到一个合法的括号序列,同时需要使得代价之和最小。

  • 数据输入

文件有多个测试实例(\leq 5)。每个实例的第一行有 1 个正整数 n,(1 \leq n \leq 100000),表示括号序列的长度为 n。第二行是一个长度为 n 的字符串,表示输入的括号序列,字符串仅由 “(”,“)” 和 “?” 组成。接下来 m 行,m 是字符串中 “?” 的个数,每一行包含两个整数 a_ib_i1 \leq a_i,b_i \leq 1000000),a_i 是将第 i 个 “?” 替换成左括号的代价,b_i 是将第 i 个 “?” 替换成右括号的代价。文件的最后一行有一个 0 表示结束。

  • 结果输出

将计算出的每个测试实例的答案依次输出到文件中。每个测试实例第一行输出一个整数,表示最小代价和。如果不存在合法方案,输出 -1。如果存在合法方案,第二行输出替换后的括号序列。若有多种替换方案的代价之和最小,可以输出任意一种。

  • 输入示例

  • 输出示例

 

 

 


 

 

 

贪心的思想,从左往右扫的时候先把每个问号设成右括号,并把 a_i-b_i 插入进堆里,当右括号数大于左括号数时说明需要把一些问号换成左括号,从堆里取出最小的 a_i-b_i 实现替换。

 

 

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注