原题链接:
计算括号(间距+1)的总和的最小值
因为缺失的地方只有奇数位,先按最小情况填完缺失的括号,然后用栈(stack)来完成总和的计算。
从第四个开始:若当前位置是 ' ) ' 且 i - 2 位置是 ' ) ' 则 i - 1 位置一定是 ' ( ' ,因为要使总值最小,必须要尽可能的两两最近匹配括号。
后面推理同理,如代码:
for(int i=1;i<n;i+=2)
if(i==1 && a[i]==')') a[0] = '(';
else if(i > 1){
if(a[i-2]==')' && a[i]==')')
a[i-1] = '(';
else if(a[i-2]=='(' && a[i]==')')
a[i-1] = ')';
else if(a[i-2]=='(' && a[i]=='(')
a[i-1] = ')';
}
for(int i=0;i<n;i+=2)
if(a[i] == '_')
a[i] = '(';
在完成3个括号的找回之后,剩下一个括号可以直接遍历填上。
在填完括号之后直接计算值即可,用 < int > 栈(stack)来存入 ' ( ' 的位置,然后当遇到 ' ) ' 的时候,用 ' ) ' 的位置去减去存进去的值,就是一段距离长度,使num去 += 这个值即可,最后输出。
直接上完整代码:
#include<bits/stdc++.h>
using namespace std;
int t,n,m,vab,num;
char a[200005];
stack <int> c;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>t;
while(t--){
cin>>n;
num = 0;
while(!c.empty()) c.pop();
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<n;i+=2)
if(i==1 && a[i]==')') a[0] = '(';
else if(i > 1){
if(a[i-2]==')' && a[i]==')')
a[i-1] = '(';
else if(a[i-2]=='(' && a[i]==')')
a[i-1] = ')';
else if(a[i-2]=='(' && a[i]=='(')
a[i-1] = ')';
}
for(int i=0;i<n;i+=2)
if(a[i] == '_')
a[i] = '(';
for(int i=0;i<n;i++){
if(a[i]=='(')
c.push(i);
else if(a[i]==')'){
num += i-c.top();
c.pop();
}
}
cout<<num<<endl;
}
return 0;
}