首页 > 代码库 > 第十五周 Leetcode 517. Super Washing Machines(HARD) 贪心
第十五周 Leetcode 517. Super Washing Machines(HARD) 贪心
Leetcode517
很有趣的一道题
由于每一步可以任选某些数字对它们进行转移，所以实际上是在求最优解中的最复杂转移数。
那么我们考虑，到底哪一个位置要经过的流量最大呢？
枚举每个位置，考虑它左边的整体需求和右边的整体需求，如果两边都需要流入，则流量相加；
如果一边需要流入，一边需要流出，则取绝对值的最大值。
复杂度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;
}
};
第十五周 Leetcode 517. Super Washing Machines(HARD) 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。