C ++中具有最高分数的最小旋转

假设我们有一个数组A，我们可以将它旋转一个K，以便数组变成A [K]，A [K + 1]，A {K + 2]，... A [A.length-1]， A [0]，A [1]，...，A [K-1]。然后，任何小于或等于其索引的条目将获得1分。

因此，例如，让我们有一个数组[2，4，1，1，3，0]，然后旋转K = 2，它变成[1、3、0、2、4]。这是值得的3分，因为1> 0 [没有获得收益]，3> 1 [没有获得收益]，0 <= 2 [获得1收益]，2 <= 3 [获得1收益]，4 <= 4 [获得4收益一点]。

我们必须找到K，为此，我们将获得最高分。如果有多个答案，则返回最小的索引K。因此，如果输入像K = 2，则答案将为5。

因此，如果输入类似于[2,3,1,5,1]，则输出将为3，这是因为-

答案将是3。

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0

• n：= A的大小

• 定义大小为n的数组cnt

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 如果A [i]> = n，则-

• minI：= i + 1

• （将cnt [minI]增加1）

• maxi：= i +（n-A [i]）

• 如果maxi + 1 <n，则-

• 忽略以下部分，跳至下一个迭代

• cnt [maxi +减少1]减1

• minI：= 0，（将cnt [minI]增加1）

• maxI：= i-A [i]

• 如果maxI + 1 <n，则-

• 如果i + 1 <n，则-

• cnt [maxI +减少1]减1

• cnt [i +增加1]加1

• 如果A [i] <= i，则-

• 除此以外

• maxCnt：= -1，温度：= 0

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• maxCnt：=温度

• ret：=我

• temp：= temp + cnt [i]

• 如果temp> maxCnt，则-

• 返回ret

让我们看下面的实现以更好地理解-

示例

#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