题目传送门
题意:
问你n辆车通过一个桥洞,等全部通过桥洞后有多少辆车超过进洞之前在自己前面的车。
解题思路:
每辆车都有自己的标记,那么先将进洞的顺序(从小到大)记录,而每辆车对应出洞的的顺序也重新记录。那么再比较它们的标记。
比如
进 汽车: 3 5 2 1 4
进 顺序 :1 2 3 4 5
出 汽车: 4 3 2 5 1
出 顺序:5 1 3 2 4
那么 超出的序好就是 5 3 而1 2 4 是按 从小到大的顺序的。
或者说你也可以这么理解: 按照进入的顺序如果比车 与比该车之前进去的车 出来的早,那么车a就超车了。
所以我们记录每个车出来的顺序,按进入的顺序进行遍历车,并记录前面的车最晚出去的顺序,如果该车出去的顺序 比最晚的早,那么该车就超车了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int MM=1e6+5;
using namespace std;
int a[MM],b[MM],out[MM],to[MM];
int main()
{
int t;
scanf("%d",&t);
for(int i=0; i<t; i++)
{
scanf("%d",a+i);
to[a[i]]=i;
}
for(int i=0; i<t; i++)
{
scanf("%d",b+i);
int ps=to[b[i]];
out[ps]=i;
}
int sum=0;
int maxx=-2;
for(int i=0; i<t; i++)
{
if(out[i]<=maxx)
sum++;
maxx=max(out[i],maxx);
}
cout<<sum<<endl;
return 0;
}