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]가 됩니다. 1> 0 [점수 없음], 3> 1 [점 없음], 0 <=2 [1점 획득], 2 <=3 [1점 획득], 4 <=4 [이득이기 때문에 이것은 3점의 가치가 있습니다. 한 점].

우리는 가장 높은 점수를 얻을 K를 찾아야 합니다. 답이 여러 개인 경우 인덱스 K 중에서 가장 작은 값을 반환합니다. 따라서 입력이 K =2와 같으면 답은 5가 됩니다.

따라서 입력이 [2,3,1,5,1]과 같으면 출력은 3이 됩니다. 이는 -

K	배열	점수
0	[2,3,1,5,1]	2
1	[3,1,5,1,2]	3
2	[1,5,1,2,4]	3
3	[5,1,2,4,1]	4
4	[1,2,4,1,3]	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

그렇지 않으면

A[i]>=n이면 -
- 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
최소I :=나는 + 1
(cnt[minI] 1 증가)
최대 :=나는 + (n - A[i])
최대값 + 1
cnt[최대값 + 1 감소] 1

maxCnt :=-1, 온도 :=0

초기화 i의 경우:=0, i

temp :=temp + cnt[i]

temp> maxCnt이면 -

maxCnt :=임시
레트 :=나

반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]