自动搬运

查看原文

来自洛谷，原作者为

	A_Big_Jiong 命是弱者的借口，运是强者的谦词。

搬运于2025-08-24 21:44:50，当前版本为作者最后更新于2018-08-29 22:24:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我实在想不明白，为什么这个题会和前缀和有关系，肯定是本蒟蒻太弱了，根本想不出来。

我的思路其实也十分简单，但由于太弱，优化是不可能优化的 （绝对不会真香警告），主要就是通过模拟栈顶，来记录有多少的括号是需修改的，具体我还是在代码中说吧。

#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;
}

这次话比较多，代码被挤得很不美观~~(虽然我这人毫无美学观念)~~，还请各位大佬多多包涵，同时，也欢迎提出新解法让我观摩。

请勿抄袭，谢谢！！！