P9805 [POI2022~2023R1] ply

1st思路

贪心

• 当遇到左括号深度加一，可如果当前深度大于 $H$ 时深度减二，并且 $ans$ 加一。相当于进行一次翻转操作。
• 当遇到右括号深度减一，当深度小于零时深度加二，并且 $ans$ 加一。

code

#include<bits/stdc++.h>
using namespace std;
string s;
int k,n=0,m=0,ans=0;
int main(){
	cin>>n>>m;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='('){
			if(k>m){k-=2;ans++;}
			k++;
		}
		if(s[i]==')'){
			if(k<0){k+=2;ans++;} 
			k--;
		}
	}
	cout<<ans;
	return 0;
}