信奥赛-刷题笔记-栈篇-T2-P3056括号调整问题0518

总题单

​

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

栈篇题单

P3056 [USACO12NOV] Clumsy Cows S

https://www.luogu.com.cn/problem/P3056

题目描述

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.
奶牛 Bessie 正在尝试在她的新笔记本电脑上输入一个平衡的括号字符串，但是由于她蹄子太大，打字时总是会按错字符。请你帮帮她：计算最少需要修改多少个括号字符（即把左括号 ( 改为右括号 )，或者反过来），才能使这个括号字符串变成平衡的括号串。
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.
第一行：一个仅由括号组成的字符串，长度不超过 100,000，且长度一定是偶数。

输出格式

* 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

2

说明/提示

The last parenthesis must be toggled, and so must one of the two middle right parentheses.
解释：可以将第一个 ) 改成 (，最后一个 ( 改成 )，得到 (()())，这是一个平衡的括号串。

思路

让我们通过一个更详细的例子来解释这个问题和解决方案。

示例输入与输出

输入

())(

输出

2

详细解释

输入字符串分析

我们有一个括号序列 ())(。为了使这个括号序列平衡，我们需要确保以下两点：

1. 整个字符串中左括号 ( 和右括号 ) 的数量相等。
2. 对于任意前缀子串，左括号的数量不少于右括号的数量。

对于给定的字符串 ())(：

• 总共有 2 个左括号 ( 和 2 个右括号 )，所以条件 1 已经满足。
• 但是，如果我们从左到右扫描字符串，我们会发现第一个字符是右括号 )，这违反了条件 2（即在任何时刻左括号的数量不能少于右括号的数量）。

因此，我们需要调整一些括号来使得整个字符串变成平衡的。

解决方案步骤

1. 初始化计数器：我们需要两个计数器，left 表示未匹配的左括号数量，right 表示未匹配的右括号数量。
2. 遍历字符串：从左到右遍历字符串中的每个字符，并根据当前字符更新计数器。
   • 如果遇到左括号 (，增加 left 计数器。
   • 如果遇到右括号 )，首先检查是否有未匹配的左括号（即 left > 0），如果有，则减少 left 计数器；如果没有，则增加 right 计数器。
3. 计算最小修改次数：最终需要修改的括号数量就是 left + right。

步骤分解

1. 初始化 left = 0, right = 0。
2. 遍历字符串 ())(：
   • 第一个字符 )：没有未匹配的左括号 (left = 0)，所以增加 right，现在 right = 1。
   • 第二个字符 )：仍然没有未匹配的左括号 (left = 0)，所以再次增加 right，现在 right = 2。
   • 第三个字符 (：增加 left，现在 left = 1。
   • 第四个字符 (：增加 left，现在 left = 2。

最终，我们有 left = 2 和 right = 2，这意味着我们需要将其中的两个右括号 ) 改为左括号 (，或者反过来。具体来说，我们可以将最后一个 ( 改为 )，并且将第一个 ) 改为 (，从而得到 (()())，这是一个平衡的括号串。

最小修改次数

因此，最少需要修改 2 个括号，使得原字符串变为平衡的括号串。

完整过程总结

1. 初始状态：left = 0, right = 0
2. 处理第一个字符 )：right = 1
3. 处理第二个字符 )：right = 2
4. 处理第三个字符 (：left = 1
5. 处理第四个字符 (：left = 2
6. 结果：left + right = 2 + 2 = 4，但由于我们可以相互抵消，实际需要修改的次数是 max(left, right) = 2。

这就是为什么对于输入 ())(，输出结果是 2。

代码1

#include <iostream>
#include <stack>
#include <cstring>using namespace std;int main() {char str[100010];cin >> str;int len = strlen(str);int ans = 0;stack<char> st;for (int i = 0; i < len; ++i) {if (str[i] == '(') {st.push('('); // 左括号入栈} else {if (st.empty()) {// 没有左括号可以匹配，必须修改这个右括号ans++;st.push('('); // 假设把这个右括号改成左括号继续匹配} else {st.pop(); // 匹配成功}}}// 剩下的都是未匹配的左括号，每两个中改一个int left = st.size();ans += left / 2;cout << ans << endl;return 0;
}
/*())( */ 

代码2

#include<cstdio>
#include<cstring>//便于使用strlen();
using namespace std;
const int maxn=100010;
char str[maxn];//我也不知道用const开数组的习惯从何而来，先这样吧
int ans,ls,num;//ans即answer,ls即str字符串的长度,num就是个假栈顶,说明现在已经有num个括号未匹配成功
int main(){scanf("%s",&str);ls=strlen(str);//记录str的长度，不要问我为什么不用STLfor(int i=0;i<ls;i++){if(str[i]=='(')  num++;//等待匹配右括号else if(str[i]==')'&&num==0){//num==0即为现在str[i]之前所有括号都能匹配，凭空出现个右括号,ans自加,并将该括号转为左括号等待匹配ans++;num++;}else num--;//匹配成功后要减少一个待匹配的数量}ans+=num/2;//还有num个左括号没有匹配,便将其中的一半转为右括号if(num%2!=0)  ans++;//如果num是单数,则有一个括号必须进行一次删除修改//值得一提的是，楼上的dalao用的ans+=(num+1)/2;和此思路一致，也更加巧妙，我太弱所以没想到printf("%d",ans);return 0;
}/*())( */ 

代码2

#include <iostream>
#include <string>
using namespace std;int main() {string s;cin >> s;int balance = 0, ans = 0;for (char c : s) {// 如果为( 则balance++if (c == '(') balance++;else { // 说明是)// 如果balance为0 说明没有 ( 那么出现)是有问题的if (balance == 0) {ans++;         // 多了一个右括号，强制改成左括号balance = 1;     // 添加一个虚拟的左括号用于后续匹配} else {balance--; // )和( 匹配 balance--}}}ans += balance / 2; //最终还剩余的左括号( 需要把一半换为 右括号) 添加到答案中cout << ans << endl;return 0;
}

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：FILE freopen( const char path, const char mode, FILE stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}