C++ এ সর্বোচ্চ স্কোর সহ ক্ষুদ্রতম ঘূর্ণন

ধরুন আমাদের একটি অ্যারে রয়েছে, আমরা এটিকে একটি 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 =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