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_i\) 和 \(b_i\)(\(1 \leq a_i,b_i \leq 1000000\)),\(a_i\) 是将第 \(i\) 个 “?” 替换成左括号的代价,\(b_i\) 是将第 \(i\) 个 “?” 替换成右括号的代价。文件的最后一行有一个 \(0\) 表示结束。

  • 结果输出

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

  • 输入示例

  • 输出示例

 

 

 


 

 

 

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

 

 

 

发表回复

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