CF 187A(从后取数的重排数列)

内容目录

题目大意:一串数,每次把最后那个数挪到前面任意位置,就最少挪动次数

显然一个数最多挪一次(只能从后取的话,插2次的一定能变成1次)

因此找最后挪动的数即可,最后挪动的数即由于与下序列的连线与之前的交叉,其它数无论怎么挪都无法影响到它)

Program DD;
const
   maxn=200000;
var
   n,i,j,l,r:longint;
   a,b,hposa,hposb:array[1..maxn] of longint;
begin
   read(n);
   for i:=1 to n do
   begin
      read(a[i]);
      hposa[a[i]]:=i;
   end;
   for i:=1 to n do
   begin
      read(b[i]);
      hposb[b[i]]:=i;
   end;
   r:=0;
   for i:=1 to n do
   begin
       if r<hposb[a[i]] then r:=hposb[a[i]]
       else break;
   end;
   if (r=hposb[a[i]]) then writeln('0') else
   writeln(n-i+1);

end.