C++で配列を互いに素な間隔に分割する

配列Aがあるとすると、-

• 左側のサブアレイのすべての要素は、右側のサブアレイのすべての要素以下です。

• 左右のサブアレイは空ではありません。

• 左側のサブアレイのサイズは可能な限り最小です。

このような分割後の残りの長さを見つける必要があります。そのようなパーティショニングが存在することが保証されています。

したがって、入力が[5,0,3,8,6]の場合、左の配列は[5,0,3]になり、右のサブ配列は[8,6]になるため、出力は3になります。

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

• n：=Aのサイズ、サイズnの配列maxxを作成します

• minVal：=Aの最後の要素

• maxx [0]：=A [0]

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

  • maxx [i]：=A[i]とA[i– 1]

    の最大値

• ans：=Aのサイズ– 1

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

  • minVal：=minValとA[i]

    の最小値

  • minVal> =max [i – 1]の場合、ans：=i

• ansを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int partitionDisjoint(vector <int>& A) {
      int n = A.size();
      vector <int> maxx(n);
      int minVal = A[n - 1];
      maxx[0] = A[0];
      for(int i = 1; i < n; i++){
         maxx[i] = max(A[i], maxx[i - 1]);
      }
      int ans = A.size() - 1;
      for(int i = n - 1; i >= 1; i--){
         minVal = min(minVal, A[i]);
         if(minVal >= maxx[i - 1]){
            ans = i;
         }
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {5,0,3,8,6};
   Solution ob;
   cout << (ob.partitionDisjoint(v1));
}

入力

[5,0,3,8,6]

出力

3