C++ में उच्चतम स्कोर के साथ सबसे छोटा रोटेशन (Smallest Rotation with Highest Score)

मान लीजिए हमारे पास एक ऐरे 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, 3, 0] है, और हम K = 2 से घुमाते हैं, यह [1, 3, 0, 2, 4] बन जाता है। यह 3 अंक के लायक है क्योंकि 1 > 0 [कोई अंक नहीं], 3 > 1 [कोई अंक नहीं], 0 <= 2 [एक अंक प्राप्त], 2 <= 3 [एक अंक प्राप्त], 4 <= 4 [एक अंक प्राप्त]।

हमें वह 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 < n, i बढ़ाते हुए, करें -
- यदि A[i] <= i, तो -
  - minI := 0, (cnt[minI] को 1 से बढ़ाएं)
  - maxI := i - A[i]
  - यदि maxI + 1 < n, तो -
    - cnt[maxI + 1] को 1 से घटाएं
  - यदि i + 1 < n, तो -
    - cnt[i + 1] को 1 से बढ़ाएं
- अन्यथा
  - यदि A[i] >= n, तो -
    - अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
  - minI := i + 1
  - (cnt[minI] को 1 से बढ़ाएं)
  - maxi := i + (n - A[i])
  - यदि maxi + 1 < n, तो -
    - cnt[maxi + 1] को 1 से घटाएं
maxCnt := -1, temp := 0
i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- temp := temp + cnt[i]
- यदि temp > maxCnt, तो -
  - maxCnt := temp
  - ret := i
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]