การหมุนเล็กที่สุดที่ให้คะแนนสูงสุด (Smallest Rotation with Highest Score) ใน C++

ภาพรวมปัญหา

สมมติว่าเรามีอาร์เรย์ A เราสามารถหมุนมันโดย K ทำให้อาร์เรย์กลายเป็น A[K], A[K+1], ..., A[n-1], A[0], A[1], ..., A[K-1] กฎการให้คะแนน: สมาชิกที่มีค่าน้อยกว่าหรือเท่ากับดัชนี (index) ของมัน จะได้ 1 คะแนน

ตัวอย่าง

A = [2, 3, 1, 5, 1]

K	Array	Score
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

คำตอบคือ K = 3 (คะแนนสูงสุด 4 คะแนน)

แนวทางแก้ปัญหา (Difference Array / Prefix Sum)

สำหรับแต่ละสมาชิก A[i] คำนวณช่วง K ที่ทำให้ A[i] ได้คะแนน
ใช้ difference array (cnt) บันทึกการเปลี่ยนแปลงคะแนนเมื่อ K เปลี่ยน
คำนวณ prefix sum หา K ที่ให้คะแนนสูงสุด (ถ้าเท่ากันเลือก K น้อยสุด)

ตัวอย่างโปรแกรม

#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, temp = 0;
        for(int i = 0; i < n; i++) {
            temp += cnt[i];
            if(temp > maxCnt) {
                maxCnt = temp;
                ret = i;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,3,1,5,1};
    cout << (ob.bestRotation(v));
}

Input