min movements to move products

这题的答案看不明白。我发了stackoverflow, 但被closed. 希望有人解答一下。


https://stackoverflow.com/questi...nt-to-move-products


Example:
[3_products, 4_products, 6_xxx, 6_xxx, 6_xxx] (index is 1 based; not 0 based)
3 -> 4 -> 6 -> 6 -> 6 (in a cycle)


option 1:
start at index 3th, clockwise
5th -> 1th, cost = 1
4th -> 1th, cost = 2
3rd -> 2nd, cost = 4
each container has 5, total_cost = 1+2+4 = 7


option 2:
start at index 5th, anti-clockwise
3rd -> 1th, cost = 2
4th -> 1th, cost = 3
5th -> 2nd, cost = 3
each container has 5, total_cost = 2+3+3 = 8
7 <= 8, so ans is 7

int getCost(const int n, const vector<int>& a, const int target) {
    int cost = 0, balance = 0, minBalance = 0;
    for (const auto x : a) {
        balance += x - target;
        minBalance = min(minBalance, balance);
        cost += balance;
    }
    return cost - minBalance * n;
}

int solve(vector<int>& a) {
    const int n = (int)a.size(), target = reduce(a.cbegin(), a.cend()) / n;
    const int cw = getCost(n, a, target);
    ranges::reverse(a);
    const int ccw = getCost(n, a, target);
    return min(cw, ccw);
}

int main() {
    vector a {6,6,6,4,3};
    cout << solve(a) << endl; // 7
}

There a few lines which I don't understand:


minBalance = min(minBalance, balance); why do we need to find out the minBalance?


cost += balance; balance1 = point1, balance2 = point1 + point2, balanceN = point1 + ..pointN. Why is this "cost"?


cost - minBalance * n? What is minBalance*n? Why do we take it off from cost?






reference:
https://leetcode.com/discuss/int...new-grad-oa/2648819
https://leetcode.com/discuss/int...zon-OA-question-SDE