2019牛客暑期多校训练营（第一场）a题目

这道题的含义就是在两个数组中，区间相同时最小的元素的位置是相同的，我们这道题用单调递增栈做，保证在栈中元素是单调递增的，

用一个整型变量k来记录，k的初始值是1（因为第一个元素是提前入栈的，当栈中只有一个元素时，k为1），最后输出k,当栈中的元素个数

是相同的时候，k就加一，当不相同的时候就输出k值。

因为题目的要求时输出的是两个数组中从a1,b1开始到ap,bp,这时最小元素的索引不相同。然后输出的时p值

而单调栈就可以从小到大存储，然后当进入的数比栈顶元素大时，就直接入栈；当进入的数比栈顶元素小时，栈顶元素出栈，一直到比栈顶

元素大，就进栈，这样的话，该区间的最小的元素都被存储起来，而那些数值较大的元素就不管。

#include<iostream> 
#include<stack>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int a[100005],b[100005];
        stack<int>A,B;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&b[i]);
            A.push(a[0]);
            B.push(b[0]); 
            int k=1;
        while(1){
           if(k==n){
               printf("%d\n",n);
               break;
           } 
                while(1){
                    if(!A.empty()){
                        if(a[k]<A.top())
                            A.pop();
                        else{
                                A.push(a[k]);
                                break;
                        }
                    
                    }
                    else{
                        A.push(a[k]);
                        break;
                    }
                }
                    while(1){
                    if(!B.empty()){
                        if(b[k]<B.top())
                            B.pop();
                        else{
                                B.push(b[k]);
                                break;
                        }
                    
                    }
                    else{
                        B.push(b[k]);
                        break;
                    }
                }
            if(A.size()==B.size())//栈中进一个元素就比较一次，更新k值
                    k++;
            else{
                    printf("%d\n",k);
                    break;
            }
        }
    }
    return 0;
}