การหมุนน้อยที่สุดด้วยคะแนนสูงสุดใน C++

สมมติว่าเรามีอาร์เรย์ A เราอาจหมุนมันด้วย K เพื่อให้อาร์เรย์กลายเป็น A[K], A[K+1], A{K+2], ... A[A.length - 1], เอ[0],เอ[1], ...,เอ[K-1]. จากนั้น รายการใดๆ ที่น้อยกว่าหรือเท่ากับดัชนีจะมีมูลค่า 1 คะแนน

ตัวอย่างเช่น ให้เรามีอาร์เรย์ [2, 4, 1, 3, 0] และเราหมุนด้วย K =2 มันจะกลายเป็น [1, 3, 0, 2, 4] มีค่า 3 แต้ม เพราะ 1> 0 [ไม่ได้แต้ม], 3> 1 [ไม่ได้แต้ม], 0 <=2 [ได้ 1 แต้ม], 2 <=3 [ได้ 1 แต้ม], 4 <=4 [ได้แต้ม] หนึ่งคะแนน].

เราต้องหา K ให้ได้ ซึ่งเราจะได้คะแนนสูงสุด หากมีหลายคำตอบ ให้คืนค่าดัชนี K ที่เล็กที่สุด ดังนั้นหากอินพุตเป็น K =2 คำตอบจะเป็น 5

ดังนั้นหากอินพุตเป็น [2,3,1,5,1] เอาต์พุตจะเป็น 3 นั่นเป็นเพราะ −

คำตอบจะเป็น 3.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0
• n :=ขนาดของ A
• กำหนดอาร์เรย์ cnt ของขนาด n
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• ถ้า 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