题目链接:https://vjudge.net/problem/CodeForces-1237B
题目大意:给你两个长度为n的数列,看看第二个数列有多少数在原数列数字的前面
从原数列的角度出发,第二个数列中和原数列相等的数前面多出来的数就是移动后的数
#include<set> #include<map> #include<list> #include<stack> #include<queue> #include<cmath> #include<cstdio> #include<cctype> #include<string> #include<vector> #include<climits> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define endl '\n' #define rtl rt<<1 #define rtr rt<<1|1 #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define maxx(a, b) (a > b ? a : b) #define minn(a, b) (a < b ? a : b) #define zero(a) memset(a, 0, sizeof(a)) #define INF(a) memset(a, 0x3f, sizeof(a)) #define IOS ios::sync_with_stdio(false) #define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n") using namespace std; typedef long long ll; typedef pair<int, int> P; typedef pair<char, int> P2; const double pi = acos(-1.0); const double eps = 1e-7; const ll MOD = 1000000007LL; const int INF = 0x3f3f3f3f; const int _NAN = -0x3f3f3f3f; const double EULC = 0.5772156649015328; const int NIL = -1; template<typename T> void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } const int maxn = 1e5+10; int a[maxn], b[maxn], vis[maxn]; int main(void) { int n; scanf("%d", &n); for (int i = 0; i<n; ++i) scanf("%d", &a[i]); for (int i = 0; i<n; ++i) scanf("%d", &b[i]); int l = 0, ans = 0; for (int i = 0; i<n && l<n-1; ++i) { //对第二数列的最后一个数比较是没有意义的,所以n-1 if (vis[a[i]]) continue; while(l<n-1 && a[i]!=b[l]) { vis[b[l++]] = true; //对移出去的数字做标记 ++ans; } b[l++] = true; //此时两数列的两个数相等,移动到下一个位置进行比较 } printf("%d\n", ans); return 0; }