C++でシーケンスを増やすための最小スワップ

したがって、入力がA=[1,3,5,4]およびB=[1,2,3,7]の場合、A[3]をB[3]と交換すると、答えは1になります。その場合、シーケンスはA=[1,3,5,7]およびB=[1,2,3,4]になり、どちらも厳密に増加します。

これを解決するには、次の手順に従います-

• n：=A配列のサイズ、それぞれサイズnの2つの配列swapCntとnoSwapCntを作成します

• swapCntに1を挿入し、noSwapCntに0を挿入します

• 1からn–1の範囲のiの場合

  • swapCnt [i]：=nおよびnoSwapCnt：=n

  • A [i]> A [i –1]かつB[i]> B [i – 1]の場合、

    • noSwapCnt [i]：=noSwapCnt [i – 1]

    • swapCnt [i]：=swapCnt [i – 1] + 1

  • A [i]> B [i –1]およびB[i]> A [i – 1]の場合、

    • swapCnt [i]：=最小のswapCnt [i]、1 + noSwapCnt [i – 1]

    • noSwapCnt [i]：=最小のswapCnt [i – 1]、noSwapCnt [i]

• swapCnt [n – 1]、noSwapCnt [n – 1]

  の最小値を返します

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSwap(vector<int>& A, vector<int>& B) {
      int n = A.size();
      vector <int> swapCnt(n), noSwapCnt(n);
      swapCnt[0] = 1;
      noSwapCnt[0] = 0;
      for(int i = 1; i < n; i++){
         swapCnt[i] = n;
         noSwapCnt[i] = n;
         if(A[i] > A[i - 1] && B[i] > B[i - 1]){
            noSwapCnt[i] = noSwapCnt[i - 1];
            swapCnt[i] = swapCnt[i - 1] + 1;
         }
         if(A[i] > B[i - 1] && B[i] > A[i - 1]){
            swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
            noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
         }
      }
      return min(swapCnt[n - 1], noSwapCnt[n - 1]);
   }
};
main(){
   vector<int> v1 = {1,3,5,4};
   vector<int> v2 = {1,2,3,7};
   Solution ob;
   cout << (ob.minSwap(v1, v2));
}

入力

[1,3,5,4]
[1,2,3,7]

出力

1