注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
这题的答案看不明白。我发了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 |