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