517. Super Washing Machines

▶ 超级洗碗机。给定一个有 n 元素的整数数组，我们把 “将指定位置上元素的值减 1，同时其左侧或者右侧相邻元素的值加 1” 称为一次操作，每个回合内，可以选定任意 1 至 n 个位置进行独立的操作，求最少的回合数，使得该数组中的搜有元素调整为相等的值。若不存在（所有元素的和不能被元素个数整除），返回 -1 。

● 代码，14 ms，最大差距法。考虑将所有元素的平均值平移到 0，记此时 machines[ 0 ] == a，如果 a == 0，则 machines[ 0 ]已经调整完成，跳过；若 a ＞ 0，则考虑对 machines[ 0 ] 做 a 次操作将多余部分转移到 machines[ 1 ] 上；若 a ＜ 0，则考虑对 machines[ 1 ] 做 a 次操作，补充 machines[ 0 ] 缺少的部分。然后对 machines[1] 做相同的分析，以此类推向后处理。发现在这一过程中，所需的最大回合数实际上取决于两个数：①某个元素本身的绝对值大小（如所有元素都是0，只有一个元素为 10000，则回合数取决于该值）；②从 machines[ 0 ] 开始积累到该元素为止的（比如前三个元素为分别为 1，2，3，则分析 machines[3] 时前面已经积累了 6 个单位，至少需要 6 回合才能消灭这个峰）。

 1 class Solution
 2 {
 3 public:
 4     int findMinMoves(vector<int>& machines)
 5     {
 6         const int n = machines.size();
 7         int i, total, average, count, maxnum;
 8         for (i = total = 0; i < n; total += machines[i++]);
 9         if (total % n)
10             return -1;
11         for (average = total / n, i = count = maxnum = 0; i < n; i++)
12         {
13             count += machines[i] - average;// 计算当前格点和平均值的差距
14             maxnum = max(max(maxnum, abs(count)), machines[i] - average);// 比较历史maxnum，累计差距，当前差距中最大者
15         }
16         return maxnum;
17     }
18 };

● 逐格分析，14 ms

■ 先计算数组 machiunes 的累积和 sum，可以用其最后一个元素来计算平均值以及判断是否有解

■ 对于第 i 个格点，计算其左侧编号为 0 ~ i-1 的 i 个格点的数值需求量（i * avg） - 数值保有量（sum[i]），记作 lp

■ 其右侧编号为 i+1 ~ machines.size()-1 的 n-1-i 个格点类似处理，结果记作 rp

■ 若 lp > 0 && rp > 0，说明两边都缺货，应该从第 i 格点往两边分配，需要 abs(lp) + abs(rp) 回合

■ 若 lp < 0 && rp < 0，说明两边都有富余，应该从两边向第 i 格点分配，需要 max(abs(lp), abs(rp)) 回合

■ 若 lp < 0 && rp > 0 || lp > 0 && rp < 0，说明两侧不均等，需要借助第 i 格点进行传递，需要 max(abs(L), abs(rp)) 回合

 1 class Solution
 2 {
 3 public:
 4     int findMinMoves(vector<int>& machines)
 5     {
 6         const int len = machines.size();
 7         int i, avg, res, lp, rp;
 8         vector<int> sum(len + 1, 0);
 9         for (i = 0; i < len; i++)// 累积和
10             sum[i + 1] = sum[i] + machines[i];
11         if (sum[len] % len)
12             return -1;
13         for (avg = sum[len] / len, i = res = 0; i < len; i++)
14         {
15             lp = i * avg - sum[i];
16             rp = (len - i - 1) * avg - (sum[len] - sum[i] - machines[i]);
17             if (lp > 0 && rp > 0)
18                 res = max(res, abs(lp) + abs(rp)); 
19             else
20                 res = max(res, max(abs(lp), abs(rp)));
21         }
22         return res;
23     }
24 };