UVa 13152 Balanced String

题目分析本题是一个经典的括号序列还原问题给定一个打乱后的前缀差值序列要求还原出字典序最小的原始平衡括号串。问题重述对于一个合法的括号串我们从左到右扫描每扫描一个字符就计算当前已扫描的(数量减去)数量得到一个差值序列。然后将这个序列随机打乱。现在给定打乱后的序列要求判断是否存在一个合法的括号串能够产生这个序列经过打乱后匹配如果存在输出字典序最小的那个括号串如果不存在输出invalid关键观察序列的性质起始差值为000最终差值为000扫描过程中差值始终≥0\ge 0≥0括号串合法的必要条件每次变化为1遇到(或-1遇到)输入序列的特征最小值必须为000因为有起始的000最大值不能超过N/2N/2N/2因为最多N/2N/2N/2个(深度不可能超过这个数NNN必须为偶数平衡串要求左右括号数相等频率数组的作用将输入序列排序后可以得到每个差值出现的次数freq[d]这个频率数组刻画了扫描路径经过每个深度的次数解题思路算法核心思想我们可以模拟扫描过程每一步决定放(还是)同时维护当前深度cur和频率数组freq。为了保证字典序最小我们优先尝试放(。详细步骤步骤 1输入预处理读取NNN和序列统计每个数字出现的次数存入freq数组记录最小值和最大值步骤 2可行性初步检查如果NNN是奇数→\rightarrow→invalid如果最小值≠0\neq 00→\rightarrow→invalid如果最大值N/2 N/2N/2→\rightarrow→invalid步骤 3模拟构造过程初始化cur 0当前深度leftRemain N/2剩余可放的(数量ans 结果字符串对于step0step 0step0到N−1N-1N−1尝试放(的条件下一个深度cur1在频率数组中还有剩余(freq[cur1] 0)还有剩余的(可用(leftRemain 0)隐含条件放(后未来的路径还能合法走完这里通过频率数组保证——因为freqfreqfreq是从合法路径得到的只要按频率消耗最终一定能回到000如果满足条件放(ans (freq[cur1]--curleftRemain--否则尝试放)要求当前深度0 00且freq[cur-1] 0放)ans )freq[cur-1]--cur--如果两个都不满足说明无法继续标记为invalid。步骤 4最终检查如果过程中没有出现invalid且最后cur0cur 0cur0则构造成功否则输出invalid正确性证明可行性频率数组freq记录了每个深度被经过的次数模拟过程按照频率消耗只要每一步的深度变化是连续的111或−1-1−1最终一定能回到000因为起始和结束都是深度000总步数为NNN变化次数对称。字典序最小每一步优先尝试放(因为()这样构造出的字符串在字典序上是最小的。时间复杂度O(N)O(N)O(N)因为只需一次扫描构造频率数组大小与NNN无关但最大深度≤N/2\le N/2≤N/2。示例验证样例 1输入2 4 0 0 1 1 5 1 2 3 4 5输出Case 1: ()() Case 2: invalid解释Case 1\texttt{Case 1}Case 1freq[0] 2,freq[1] 2模拟构造得到()()Case 2\texttt{Case 2}Case 2最小值不为000直接invalid注意事项频率数组要开足够大至少maxVal 2避免越界整数范围在 32 位有符号内但实际值不会超过N/2N/2N/2字典序比较中()代码实现// Balanced String// UVa ID: 13152// Verdict: Accepted// Submission Date: 2026-02-28// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;for(intcaseNum1;caseNumT;caseNum){intN;cinN;vectorintseq(N);mapint,intfreqMap;intminValINT_MAX,maxValINT_MIN;for(inti0;iN;i){cinseq[i];freqMap[seq[i]];if(seq[i]minVal)minValseq[i];if(seq[i]maxVal)maxValseq[i];}// 初步检查if(N%2!0||minVal!0||maxValN/2){coutCase caseNum: invalid\n;continue;}// 转成数组方便索引vectorintfreq(maxVal2,0);for(autop:freqMap){if(p.firstmaxVal)continue;freq[p.first]p.second;}// 模拟构造string ans;intcur0;intleftRemainN/2;boolvalidtrue;for(intstep0;stepN;step){// 尝试放 (if(cur1maxValfreq[cur1]0leftRemain0){ans.push_back(();freq[cur1]--;cur;leftRemain--;}elseif(cur0freq[cur-1]0){// 放 )ans.push_back());freq[cur-1]--;cur--;}else{validfalse;break;}}if(!valid||cur!0){coutCase caseNum: invalid\n;}else{coutCase caseNum: ans\n;}}return0;}