Powered by:NEFU AB-IN

Link

4367. 拍照2

• 题意

  农夫约翰有 N 头奶牛，编号 1∼N。
  约翰让它们排成一排，以便拍照。
  最初，奶牛从左到右按照 a1,a2,…,aN 的顺序排列。
  但是，约翰希望奶牛从左到右按照 b1,b2,…,bN 的顺序排列。
  为此，他需要对队列进行一系列的调整操作。
  每次操作可以选择任意一头奶牛并将其向左移动一些位置。
  请问，至少需要多少次操作，才能使奶牛按照约翰满意的顺序排列。

• 思路

  从左到右开始匹配 , A[] 和 B[] :

  • 如果 A[0] != B[0] : 那么在 A[] 中的 B[0] 需要进行这次操作移到最前面。
  • 如果 A[0] == B[0] : 那么直接匹配即可
  • 然后递归执行 A[1:] 和 B[1:] 的匹配过程

  那么，如果能匹配上，就都往后移；如果不能匹配上，可以存入$set$，用来记录，这个元素已经被标记过了

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-06-27 16:06:31
  * @FilePath: \ACM\Acwing\4367\4367.cpp
  * @LastEditTime: 2022-06-27 16:51:35
  */
  #include 
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
      IOS;
      int n, a;
      cin >> n;
  
      vector<int> b(n);
      for (int i = 0; i < n; i++)
          cin >> b[i];
  
      set<int> st;
      for (int i = 0, j = 0; i < n; i++)
      {
          cin >> a;
          while (st.count(b[j]))
              j++;
          if (b[j] == a)
              j++;
          else
              st.insert(a);
      }
      cout << st.size() << "\n";
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44