蹲一下第二题大家的思路

第二题可以直接遍历每个字符，并且记录当前位置之前的 ( 的个数 = left，如果当前位置为 ) 则看前面是否 left > 0，是的话则 left-- 然后继续遍历下一个字符；如果 left = 0 则前面没有 ( 了，此时向后面找第一个 ( 的位置，交换这两个字符并记录交换次数，然后继续遍历即可；这样可以解决 81% 会超时，为了减少查找次数可以在向后找第一个 ( 时维护当前的位置，下次直接从记录的位置向后找，这样就不超时了，但还是81%，此时把总交换次数的类型从 int 换成 long 就能100%

#include <iostream> (30316)#include<stack> #include<unordered_map> (30194)#include<vector> using namespace std; int main() { int n; cin>>n; while(n--) { int a; cin>>a; unordered_map<char,int>pos; pos['(']=0; pos[')']=0; int ans=0; for(int i=0;i<a;i++) { char s; cin>>s; if(s==')') { if(pos['(']!=0) pos['(']--; else pos[')']++;; } else { if(pos[')']!=0) { ans+=pos[')']; pos[')']--; } else { pos['(']++; } } } cout<<ans<<'\n'; } } 这是我的代码，不过要把int 改成long long 不然只过百分之八十 大概就是贪心加线性扫描。无需模拟，只在扫描过程中计算每个左括号为了修复前面失衡，需要跨过多少个右括号

贪心，然后额外维护一个（的位置指针就行了