Quay vòng nhỏ nhất cho điểm cao nhất (Smallest Rotation with Highest Score) trong C++

Cho mảng A, quay vòng trái K vị trí. Điểm = số phần tử A[i] ≤ i (sau khi quay). Tìm K nhỏ nhất cho điểm lớn nhất.

Ví dụ

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

Kết quả: K = 3.

Thuật toán hiệu quả O(n)

Dùng mảng hiệu cnt để tính điểm cho mọi K trong O(n). Với mỗi phần tử A[i], xác định khoảng K mà nó đóng góp điểm, cập nhật cnt bằng kỹ thuật difference array.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int bestRotation(vector<int>& A) {
        int n = A.size();
        vector<int> cnt(n, 0);
        for(int i=0; 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, ret = 0;
        for(int i=0; i maxCnt) { maxCnt = temp; ret = i; }
        }
        return ret;
    }
};

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