您的当前位置:首页正文

Educational Codeforces Round 168 (Rated for Div. 2) Problem C

2024-12-01 来源:个人技术集锦

原题链接: 

题目大意理解:

计算括号(间距+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;
}

显示全文