C++で最高のスコアを持つ最小のローテーション

配列Aがあるとすると、配列がA [K]、A [K + 1]、A {K + 2]、... A [A.length-1]になるように、Kだけ回転させることができます。 A [0]、A [1]、...、A[K-1]。次に、インデックス以下のエントリは1ポイントの価値があります。

たとえば、配列[2、4、1、3、0]があり、K =2だけ回転すると、[1、3、0、2、4]になります。これは3ポイントの価値があります。1>0[ポイントなし]、3> 1 [ポイントなし]、0 <=2 [1ポイント獲得]、2 <=3 [1ポイント獲得]、4 <=4[ポイント獲得ワンポイント]。

Kを見つける必要があります。Kを見つけると、最高のスコアが得られます。複数の回答がある場合は、そのような最小のインデックスKを返します。したがって、入力がK =2の場合、回答は5になります。

したがって、入力が[2,3,1,5,1]の場合、出力は3になります。これは、-

答えは3になります。

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

• ret：=0
• n：=Aのサイズ
• サイズnの配列cntを定義します
• iを初期化する場合：=0、i
• A [i] <=iの場合、-
  • minI：=0、（cnt [minI]を1増やします）
  • maxI：=i --A [i]
  • maxI + 1
  • cnt[maxI+1減少1]
• i + 1
• cnt[i+1を1増やす

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int bestRotation(vector<int>& A) {
      int ret = 0;
      int n = A.size();
      vector <int> cnt(n);
      for(int i = 0; i < n; i++){
         if(A[i] <= i){
            int minI = 0;
            cnt[minI]++;
            int maxI = i - A[i];
            if(maxI + 1 < n) cnt[maxI + 1]--;
            if(i + 1 < n) cnt[i + 1]++;
         }else{
            if(A[i] >= n) continue;
            int minI = i + 1;
            cnt[minI]++;
            int maxi = i + (n - A[i]);
            if(maxi + 1 < n)cnt[maxi + 1]--;
         }
      }
      int maxCnt = -1;
      int temp = 0;
      for(int i = 0; i < n; i++){
         temp += cnt[i];
         if(temp > maxCnt){
            maxCnt = temp;
            ret = i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,3,1,5,1};
   cout << (ob.bestRotation(v));
}

入力

[2,3,1,5,1]

出力

3