很有趣的一道题
由于每一步可以任选某些数字对它们进行转移,所以实际上是在求最优解中的最复杂转移数。
那么我们考虑,到底哪一个位置要经过的流量最大呢?
枚举每个位置,考虑它左边的整体需求和右边的整体需求,如果两边都需要流入,则流量相加;
如果一边需要流入,一边需要流出,则取绝对值的最大值。
复杂度O(n)
class Solution {
public:
int findMinMoves(vector<int>& machines) {
int len = machines.size();
vector<int> sum(len + 1, 0);
for (int i = 0; i < len; ++i)
sum[i + 1] = sum[i] + machines[i]; if (sum[len] % len) return -1; int avg = sum[len] / len;
int res = 0;
for (int i = 0; i < len; ++i)
{
int l = i * avg - sum[i];
int r = (len - i - 1) * avg - (sum[len] - sum[i] - machines[i]); if (l > 0 && r > 0)
res = std::max(res, std::abs(l) + std::abs(r));
else
res = std::max(res, std::max(std::abs(l), std::abs(r)));
}
return res;
}
};