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\)。如果存在合法方案，第二行输出替换后的括号序列。若有多种替换方案的代价之和最小，可以输出任意一种。
-
输入示例
|
1 2 3 4 5 6 7 8 9 10 11 |
4 (??) 1 2 2 8 4 )??( 1 2 2 8 4 (()) 0 |
-
输出示例
|
1 2 3 4 5 |
4 ()() -1 0 (()) |
贪心的思想，从左往右扫的时候先把每个问号设成右括号，并把 \(a_i-b_i\) 插入进堆里，当右括号数大于左括号数时说明需要把一些问号换成左括号，从堆里取出最小的 \(a_i-b_i\) 实现替换。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } inline void getstr(char s[],int&ls) { register char c=0; while(!(c && c!=' ' && c!='\r' && c!='\n') && c!=EOF) c=getchar(); ls=0; while(c && c!=EOF && c!=' ' && c!='\r' && c!='\n') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } __gnu_pbds::priority_queue< std::pair<int,int>, std::greater< std::pair<int,int> > >pq; char s[105050]; int a[105050],b[105050],pos[105050]; int main() { register int N; re: while((N=getnum())) { int ls;getstr(s,ls); register int lq=0; for(register int i=1;i<=ls;i++) if(s[i] == '?') pos[++lq]=i,a[lq]=getnum(),b[lq]=getnum(); pq.clear(),lq=0; register int cnt=0; long long ans=0; for(register int i=1;i<=ls;i++) { if(s[i]=='(') cnt++; else if(s[i]==')') cnt--; else ++lq,s[i]=')',ans+=b[lq],pq.push(std::make_pair(a[lq]-b[lq],i)),cnt--; if(cnt<0) { if(pq.empty()) { printf("%d\n",-1); goto re; } s[pq.top().second]='(',ans+=pq.top().first,pq.pop(); cnt+=2; } } if(cnt!=0) printf("%d\n",-1); else { printf("%lld\n",ans); for(register int i=1;i<=ls;i++) putchar(s[i]); putchar('\n'); } } return 0; } |