当前位置：首页 > news >正文

CSP/信奥赛C++刷题训练：经典例题 - 栈（1）：洛谷P3056 ：[USACO12NOV] Clumsy Cows S

news 2025/7/17 10:28:26

CSP/信奥赛C++刷题训练：经典例题 - 栈（1）：洛谷P3056 ：[USACO12NOV] Clumsy Cows S

在这里插入图片描述

题目描述

Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced.

There are several ways to define what it means for a string of parentheses to be “balanced”. Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, the following strings are all balanced:

()
(())
()(()())

while these are not:

)(
())(
((())))

给出一个偶数长度的括号序列，问最少修改多少个括号可以使其平衡。

输入格式

* Line 1: A string of parentheses of even length at most 100,000 characters.

输出格式

* Line 1: A single integer giving the minimum number of parentheses that must be toggled to convert the string into a balanced string.

样例 #1

样例输入 #1

())(

样例输出 #1

提示

The last parenthesis must be toggled, and so must one of the two middle right parentheses.

AC代码

#include<bits/stdc++.h>
using namespace std;
string c;
stack<char> s;
int ans=0;
int main(){cin>>c;int n=c.size();for(int i=0;i<n;i++){if(s.size()==0){//如果栈为空 if(c[i]=='('){//左括号入栈 s.push(c[i]);} else{//右括号处理 ans++;//需更改：答案+1 s.push('(');//变成左括号入栈 }}else{//如果栈不为空 if(c[i]=='('){//左括号入栈 s.push(c[i]);} else{//右括号处理 if(s.top()=='('){s.pop();//成对就弹出 } else{ans++;//不成对，需更改：答案+1 s.push('(');//变成左括号入栈 } }} }//最后栈如果不为空，将一半变为右括号 if(!s.empty()) ans+=(s.size()+1)/2;cout<<ans;return 0;
}