noip模拟赛 括号序列
2024-08-25 12:36:07
题目描述
LYK有一个括号序列,但这个序列不一定合法。
一个合法的括号序列如下:
()是合法的括号序列。
若A是合法的括号序列,则(A)是合法的括号序列。
若A和B分别是合法的括号序列,则AB是合法的括号序列。
LYK想通过尽可能少的操作将这个不一定合法的括号序列变成合法的括号序列。一次修改操作是将某个字符变成另一个字符。
你能帮帮它吗?
输入格式(bracket.in)
一行一个字符串S。
输出格式(bracket.out)
一个数表示最少修改次数。
输入样例
()))
输出样例
1
样例解释
将第二个字符修改成(即可。
数据范围
对于30%的数据|S|<=10。
对于60%的数据|S|<=1000。
对于100%的数据|S|<=100000。且|S|是偶数。
分析:比较水的一道题,将所有符合要求的括号序列给删掉,剩下的大概长这样:)))))(((((,假设有cnt1个),cnt2个(,那么每个)转一下可以与)配对,如果是奇数个,那么肯定还要和(配对,所以答案是cnt1/2 + cnt1 % 2 + cnt2/2 + cnt2 % 2.
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; char s[];
int cnt1, cnt2, ans; int main()
{
scanf("%s", s + );
for (int i = ; i <= strlen(s + ); i++)
{
if (s[i] == '(')
cnt1++;
else
if (s[i] == ')' && cnt1)
cnt1--;
else
cnt2++;
}
ans = cnt1 / + (cnt1 % ) + cnt2 / + (cnt2 % );
printf("%d\n", ans); return ;
}
最新文章
- 【Hector slam】A Flexible and Scalable SLAM System with Full 3D Motion Estimation
- Google Java编程风格指南中文版
- Day5_作业
- android studio中the logging tag can be most 23 characters
- 使用BAPI_ACC_DOCUMENT_POST,创建会计凭证,用BADI扩展字段(转)
- extjs grid renderer用法【转载】
- Windows Embedded Compact 2013升级:VS2013也能编译
- iOS开发 AFNetworking 3.0使用遇到的问题
- A标签-一个按钮样式
- Struts2学习笔记整理(四)
- iview inoput type=textarea 禁止拉伸
- linux基础命令入门
- grid - 网格轨道对齐方式
- python3学习笔记二(注释、缩进)
- JoyOI1940 创世纪
- dsu on tree题表
- [C] 如何使用头文件 .h 编译 C 源码
- 【python】copy浅拷贝和deepcopy深拷贝
- Kafka设计解析(十四)Kafka producer介绍
- MicrosoftFixit50688 [Windows7事件ID10,WMI错误的解决方法