Minimize Maximum of Array

You are given a 0-indexed array nums comprising of $n$ non-negative integers.

In one operation, you must:

• Choose an integer $i$ such that $1 \leq i < n$ and $nums[i] > 0$.
• Decrease $nums[i]$ by $1$.
• Increase $nums[i – 1]$ by $1$.

Return the minimum possible value of the maximum integer of nums after performing any number of operations.

Example 1:

Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.

Example 2:

Input: nums = [10,1]
Output: 10
Explanation:
It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.

Constraints:

$n == nums.length$
$2 \leq n \leq {10}^{5}$
$0 \leq nums[i] \leq {10}^{9}$

解题思路

　　比赛的时候一直想着怎么用贪心去做出来，结果还是没想到。这题的话可以用二分，像最大化最小值和最小化最大值这类问题应该先想想能不能用二分来做。

　　假设最小的最大值，也就是答案为$ans$，那么根据假设小于$ans$的肯定不满足条件，因为无法构造出元素最大值小于的$ans$的序列，而大于等于$ans$是满足条件的，我们可以构造出元素最大值大于等于$ans$的序列。因此答案具有二段性，可以用二分。当二分出$mid$后，从后往前遍历数组（因为改变当前元素会对前面的元素产生变化，而对后面的元素不产生变化），如果$nums[i] > mid$，那么就把$num[i]$变成$mid$，同时$nums[i-1]$要加上$mid – nums[i]$，这样就保证了区间$[1,n-1]$最内的数的最大值不超过$mid$，最后再判断$nums[0]$是否不超过$mid$。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     bool check(vector<int> &nums, int mid) {
 4         long long t = nums.back();
 5         for (int i = nums.size() - 1; i; i--) {
 6             if (t > mid) t = t - mid + nums[i - 1];
 7             else t = nums[i - 1];
 8         }
 9         return t <= mid;
10     }
11     
12     int minimizeArrayValue(vector<int>& nums) {
13         int l = 0, r = *max_element(nums.begin(), nums.end());
14         while (l < r) {
15             int mid = l + r >> 1;
16             if (check(nums, mid)) r = mid;
17             else l = mid + 1;
18         }
19         return l;
20     }
21 };

　　当然，也是由贪心解法的。反正我遇到贪心或者思维题基本都写不出来的。

　　假设当前序列的最小的最大值为$maxv$，那么次数再往序列后面添加一个元素。如果这个元素小于等于$maxv$，那么只要我们对这个新元素进行操作，只可能会增加前面元素的最大值，而不会使得最大值变小。如果这个元素大于$maxv$，那么可以把多出来的情况均摊分给前面的元素，那么最后最小的最大值为$\left\lceil {\frac{a_0 + \cdots + a_i}{i+1}} \right\rceil$，当然这是最理想的情况，实际上不一定可以做到均分，比如序列 4,7,2,2,9 ，$\left\lceil {\frac{4+7+2+2+9}{5}} \right\rceil = 5$，实际上这个序列的最小的最大值为$6$。因此最小的最大值要$\geq \left\lceil {\frac{a_0 + \cdots + a_i}{i+1}} \right\rceil$。

　　因此我们可以从前往后遍历每一个元素，如果$nums[i] \leq maxv$，那么不做处理。如果$nums[i] > maxv$，那么更新$maxv = max(maxv, \left\lceil {\frac{a_0 + \cdots + a_i}{i+1}} \right\rceil)$（如果是$nums[i] \leq maxv$也可以做这个操作，因为得到的均值一定是比$maxv$要小的，不影响答案）。注意这里不可以直接赋值$maxv = \left\lceil {\frac{a_0 + \cdots + a_i}{i+1}} \right\rceil$，因为前面我们说过均值是最小下限，因此最小的最大值是所有最小下限的最大值。

　　AC代码如下：

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long maxv = nums[0], sum = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            sum += nums[i];
            maxv = max(maxv, (sum + i) / (i + 1));
        }
        return maxv;
    }
};

参考资料

　　两种做法：二分答案 / 分类讨论：https://leetcode.cn/problems/minimize-maximum-of-array/solution/liang-chong-zuo-fa-er-fen-da-an-fen-lei-qhee6/

原文地址：http://www.cnblogs.com/onlyblues/p/16796247.html