网站技能培训班有哪些,广告联盟排行榜,只做鞋子的网站,手机版网站建站Problem - D - Codeforces
题目大意#xff1a;给一个只包含(#xff0c;)#xff0c;?三个字符的字符串。每个?可以转为(或者)#xff0c;对于第 i i i个?转为(需要花费 a i a_i ai#xff0c;转为)需要花费 b i b_i bi。现在问能否让该字符串转为合法的括号匹配…Problem - D - Codeforces
题目大意给一个只包含()?三个字符的字符串。每个?可以转为(或者)对于第 i i i个?转为(需要花费 a i a_i ai转为)需要花费 b i b_i bi。现在问能否让该字符串转为合法的括号匹配如果可以找到最小花费并输出转为的括号匹配。
思路?的情况可以转为(也可以转为)是动态的处理起来麻烦。我们可以将?全都先转为同一种记录总花销之后根据情况替换为另一个这样虽然也是动态的但是要维护的状态少了很多。
在此将?先全部转为)对于中间态而言左边(可以多但是)数量一定小于等于左边。用括号匹配的类似操作进行计数(进行累加计数对于其他的如果是?先贪心的转为)之后让计数减一。根据计数值进行贪心的更改将原来?转)的替换为(并将计数值和字符串状态进行更新。贪心的时候需要找到中间值 i i i前面的?中 a i − b i a_i - b_i ai−bi最小那个?进行转换。
代码如下
void solve() {string s; cins;priority_queuePII heap;int n s.size();vectorarrayint,2 a(n); // (val, )valint ans 0;// 先得到 ? - ) 的总花销for(int i 0; i n; i) {if(s[i] ?) {cina[i][0]a[i][1];ans a[i][1];}}// 判断括号序列是否合法bool ok 1;int cnt 0; // 计数for(int i 0; i n; i) {if(!ok) break;if(s[i] () cnt;else {// 如果不是 ( 优先转为 ) 并计算差值cnt--;if(s[i] ?) heap.push({a[i][1] - a[i][0], i}), s[i] );// 如果是计数是负数// 将前面的 ( ? - ) ) - ( 转为 (// 并更新计数和字符串值if(cnt 0) {if(heap.size() 0) ok 0;else {auto tmp heap.top(); heap.pop();ans - tmp.first;cnt 2;s[tmp.second] (;}}}}if(cnt || !ok) puts(-1);else {coutans\n;couts\n;}
}
