2019牛客暑期多校赛（第一场） A Equivalent Prefixes（单调栈）

传送门：https://ac.nowcoder.com/acm/contest/881/A

题意：给定两个数组a和b，求最大的p，满足在区间 [1,p] 中任何区间的两个数组的最小值的下标都相等。

思路：先用单调栈，跑出数组 a 和 b 中每个元素的左边第一个比他小的数的位置和右边第一个比他小的数的位置，左边的下标加1，右边的下标减1，那么就得到了每个数字的以这个数为区间的最小值的区间。

然后再对于两个数组的每个数字的区间去遍历。对于一个总长度为n的数组来说，从第一个去开始比较，如果这两个数的左右区间界限都相等，就继续。如果左区间相等但是右区间不一样的话，那么这个时候就要缩小空间区域了，取两者中的最小值当做新的区间长度再去跑一遍过程，如果都不一样直接就跳出循环。这样一步一步缩小区间求解。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

typedef unsigned long long int ull;

const int inf = 0x3f3f3f3f;

int dir[][]={{,},{,},{,},{,-},{-,},{-,-},{,-},{-,}};

#define pi acos(-1)

#define ls rt<<1

#define rs rt<<1|1

#define me0(s) memset(s,0,sizeof(s))

#define me1(s) memset(s,1,sizeof(s))

#define mef(s) memset(s,-1,sizeof(s))

#define meinf(s) memset(s,inf,sizeof(s))

const int N=;

int la[N],ra[N],lb[N],rb[N],sta[N],stb[N],a[N],b[N];

inline int read() {

    char c=getchar(); int x=, f=;

    while(c<''|c>'') {if(c=='-') f=-;c=getchar();}

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

    return x*f;

}

ll q_pow(ll a,ll b,ll mod){

    ll anss=;

    while(b){

        if(b&) anss=anss*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return anss;

}

ll q_mul(ll a,ll b,ll mod){

    ll anss=;

    while(b){

        if(b&) anss=(anss+a)%mod;

        a=(a+a)%mod;

        b>>=;

    }

    return anss;

}

int main(int argc, char * argv[]) {

    std::ios::sync_with_stdio(false);

    int n;

    while(cin>>n){

            for(int i=;i<=n;i++) cin>>a[i];

        for(int i=;i<=n;i++) cin>>b[i];

        int top1=;

        for(int i=;i<=n;i++){

            while(top1&&a[sta[top1-]]>=a[i]){

                top1--;

            }

            la[i]=(top1==)?:sta[top1-];

            sta[top1++]=i;

        }

        top1=;

        for(int i=n;i>=;i--){

            while(top1&&a[sta[top1-]]>=a[i]) top1--;

            ra[i]=(top1==)?(n+):sta[top1-];

            sta[top1++]=i;

        }

        int top2=;

        for(int i=;i<=n;i++){

            while(top2&&b[stb[top2-]]>=b[i]){

                top2--;

            }

            lb[i]=(top2==)?:stb[top2-];

            stb[top2++]=i;

        }

        top2=;

        for(int i=n;i>=;i--){

            while(top2&&b[stb[top2-]]>=b[i]) top2--;

            rb[i]=(top2==)?(n+):stb[top2-];

            stb[top2++]=i;

        }

        for(int i=;i<=n;i++){

            la[i]=la[i]+;

            ra[i]=ra[i]-;

            lb[i]=lb[i]+;

            rb[i]=rb[i]-;

        }

        // for(int i=1;i<=n;i++){

        //     cout<<la[i]<<" "<<ra[i]<<" "<<lb[i]<<" "<<rb[i]<<endl;

        // }

        for(int i=;i<=n;i++){

            if(la[i]==lb[i]&&ra[i]==rb[i]){

                continue;

            }

            else if(la[i]==lb[i]&&ra[i]!=rb[i])

                n=min(ra[i],rb[i]);

            else break;

        }

        cout<<n<<endl;

    }

    return ;

}

巴特西

2019牛客暑期多校赛（第一场） A Equivalent Prefixes（单调栈）

最新文章

热门文章