C/C++教程

AcWing 2003. 找到牛!

本文主要是介绍AcWing 2003. 找到牛!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意

给定一个括号字符串,连续的两个'('可以表示牛的前脚,连续的两个')'可以表示牛的后脚,前脚必须在后脚的左侧,求牛的可能位置有几个,牛的可能位置由他的前后脚表示。

数据范围

\(1 \le N \le 50000\)

解题思路

  • 正解是\(O(n)\)的做法,记一下当前位置及以前的"(("的对数,判断当前位置是否为"))",如果是"))",答案加上之前的"(("数量。

  • 我的做法是处理出来所有的"(("和"))"的位置,前者是记录第二个字符的位置,后者记录第一个字符的位置,然后枚举左括号的位置,二分查找可以与之匹配的右括号数量,加到答案上。但该方法复杂度为\(O(n\log{n})\),且边界容易出错。

代码

方法一:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;

char s[N];

int main()
{
    scanf("%s", s);
    int n = strlen(s);
    
    int cnt = 0, ans = 0;
    for(int i = 1; i < n; i ++){
        if(s[i] == '(' && s[i - 1] == '(') cnt ++;
        if(s[i] == ')' && s[i - 1] == ')') ans += cnt;
    }
    printf("%d\n", ans);
    
    return 0;
}

方法二:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;

char s[N];
int l[N], r[N];

int main()
{
    scanf("%s", s);
    int n = strlen(s);
    
    int idxl = 0, idxr = 0;
    for(int i = 1; i < n; i ++){
        if(s[i] == '(' && s[i - 1] == '(') l[idxl ++] = i;
    }
    for(int i = n - 2; i >= 0; i --){
        if(s[i] == ')' && s[i + 1] == ')') r[idxr ++] = i;
    }
    sort(r, r + idxr);
    
    int ans = 0;
    for(int i = 0; i < idxl; i ++){
        int x = l[i];
        int ll = 0, rr = idxr - 1;
        while(ll < rr){
            int mid = ll + rr + 1 >> 1;
            if(r[mid] <= x) ll = mid;
            else rr = mid - 1;
        }
        if(r[ll] > x) ans += idxr - ll;
        else ans += idxr - ll - 1;
    }
    printf("%d\n", ans);
    
    return 0;
}
这篇关于AcWing 2003. 找到牛!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!