AcWing 2003. 找到牛！——O(N)做法详解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2003. 找到牛！——O(N)做法详解原题链接简单

作者：

Kx233 , 2022-04-24 21:05:07 , 所有人可见 , 阅读 1259

38

8

因为N<=50000 所以O(n^2)做法可能会超时
但是我们可以先统计遍历中看到的后腿数量
之后每一次出现的前腿都可以匹配到
所以我们在每次发现前腿时都将ans加上cnt

#include <iostream>
using namespace std;
int main()
{
    string s; cin>>s;
    int ans=0, cnt=0;
    for(int i=1; i<s.size(); i++)
    {
        if(s[i-1]==')' && s[i]==')') ans+=cnt;//发现前腿
        else if(s[i-1]=='(' && s[i]=='(') cnt++;//发现后腿
    }
    cout<<ans;
    return 0;
}