首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >信奥赛-刷题笔记-栈篇-T2-P3056括号调整问题0518

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

原创
作者头像
IT从业者张某某
发布于 2025-05-18 12:57:00
发布于 2025-05-18 12:57:00
9200
代码可运行
举报
运行总次数:0
代码可运行

总题单

本部分总题单如下

腾讯文档】副本-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

代码语言:txt
AI代码解释
复制
())(

输出 #1

代码语言:txt
AI代码解释
复制
2

说明/提示

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

解释:可以将第一个 ) 改成 (,最后一个 ( 改成 ),得到 (()()),这是一个平衡的括号串。

思路

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

示例输入与输出

输入
代码语言:txt
AI代码解释
复制
())(
输出
代码语言:txt
AI代码解释
复制
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 = 2right = 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

代码语言:cpp
代码运行次数:0
运行
AI代码解释
复制
#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

代码语言:cpp
代码运行次数:0
运行
AI代码解释
复制
#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的长度,不要问我为什么不用STL
	for(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

代码语言:cpp
代码运行次数:0
运行
AI代码解释
复制
#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语句,

内容详见模板代码如下。

代码语言:cpp
代码运行次数:0
运行
AI代码解释
复制
#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,就可以修改标准流文件的默认值,实现重定向。

代码语言:cpp
代码运行次数:0
运行
AI代码解释
复制
#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;
}

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
array_shift() 函数
实例 删除数组中的第一个元素(red),并返回被删除元素的值: <?php $a=array("a"=>"red","b"=>"green","c"=>"blue"); echo array_s
似水的流年
2018/01/18
8650
详解PHP中array_rand函数的使用方法
array_rand() 函数返回数组中的随机键名,或者如果您规定函数返回不只一个键名,则返回包含随机键名的数组。
申霖
2019/12/27
1.2K0
详解PHP中array_rand函数的使用方法
PHP array_rand() 函数
array_rand() 函数返回数组中的随机键名,或者如果您规定函数返回不只一个键名,则返回包含随机键名的数组。
用户1448800
2021/08/19
7970
PHP array_diff() 函数
array_diff() 函数返回两个数组的差集数组。该数组包括了所有在被比较的数组中,但是不在任何其他参数数组中的键值。
用户1448800
2021/08/18
2440
PHP array_slice() 函数
实例 从数组的第三个元素开始取出,并返回数组中的其余元素: <?php $a=array("red","green","blue","yellow","brown"); print_r(array_s
用户1448800
2021/08/19
7770
PHP array_merge() 函数
注释:如果您仅向 array_merge() 函数输入一个数组,且键名是整数,则该函数将返回带有整数键名的新数组,其键名以 0 开始进行重新索引(参见下面的实例 1)。
用户1448800
2021/08/18
4240
PHP array_flip() 函数
array_flip() 函数返回一个反转后的数组,如果同一值出现了多次,则最后一个键名将作为它的值,所有其他的键名都将丢失。
用户1448800
2021/08/18
4220
php参考手册Array函数(完结了)
<?php //array_change_key_case() $age=['cyg'=>"kkk","liwen"=>"70"]; print_r(array_change_key_case($a
贵哥的编程之路
2022/05/06
2.1K0
php参考手册Array函数(完结了)
PHP array_unshift() 函数
array_unshift() 函数用于向数组插入新元素。新数组的值将被插入到数组的开头。
用户1448800
2021/08/19
3680
PHP array_shift() 函数
注释:如果键名是数字的,所有元素都会获得新的键名,从 0 开始,并以 1 递增(参见下面例子)。
用户1448800
2021/08/19
6890
PHP array_intersect() 函数
array_intersect() 函数用于比较两个(或更多个)数组的键值,并返回交集。
用户1448800
2021/08/18
3310
PHP array_udiff() 函数
array_udiff() 函数用于比较两个(或更多个)数组的键值 ,并返回差集。
用户1448800
2021/08/19
3080
PHP array_walk() 函数
array_walk() 函数对数组中的每个元素应用用户自定义函数。在函数中,数组的键名和键值是参数。
用户1448800
2021/08/20
3040
PHP常用函数总结
$x = 5.7; $y = 1.3; // 两个浮点数,x>y 浮点余数 $r = fmod($x, $y); // $r equals 0.5, because 4 * 1.3 + 0.5 = 5.7
V站CEO-西顾
2018/06/12
3.3K1
PHP 数组常用操作整理,提升工作效率
躺平程序员老修
2023/09/05
3350
Array数组函数(二)
array_count_values — 统计数组中所有的值出现的次数 1 arrayarray_count_values(array$input) array_count_values() 返回一
wangxl
2018/03/07
1K0
C++ random_shuffle函数:从兴起到被替代
在C++的发展历程中,random_shuffle函数曾是标准库中用于随机排列序列元素的重要工具。然而,随着C++语言的不断演进,这一函数也经历了从兴起、被弃用到最终被移除的过程。本文将详细回顾random_shuffle函数的使用方法、存在的问题以及其被替代的必然性,帮助你更好地理解这一函数的兴衰历程。
码事漫谈
2025/01/19
2430
C++ random_shuffle函数:从兴起到被替代
PHP array_diff_ukey() 函数
array_diff_ukey() 函数用于比较两个(或更多个)数组的键名 ,并返回差集。
用户1448800
2021/08/18
2430
PHP sort() 函数
实例 对数组 $cars 中的元素按字母进行升序排序: <?php $cars=array("Volvo","BMW","Toyota"); sort($cars); ?> 定义和用法 sort()
用户1448800
2021/08/21
6900
PHP array_push() 函数
array_push() 函数向第一个参数的数组尾部添加一个或多个元素(入栈),然后返回新数组的长度。
用户1448800
2021/08/19
4180
相关推荐
array_shift() 函数
更多 >
LV.4
这个人很懒,什么都没有留下~
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验