# 2439. Minimize Maximum of Array
https://leetcode.com/problems/minimize-maximum-of-array/description/
###### tags: `Python`,`Leetcode`

## Code

import math
class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        ans = 0
        total_sum = 0
        for i in range(len(nums)):
            total_sum += nums[i]
            ans = max( ans, math.ceil(total_sum /(i + 1)))
        return ans

## 題意
* 題目會給一個 array ，叫 `nums`
* 我們要做的是要讓 array 裡面的 maximum 盡可能減到最低，但這個減的方法比較特別，以 nums[i] 為例：
1. nums[i] value 減一
2. nums[i-1] value 加一
* 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.

## 思路
* 遍歷 `nums` 中的值，如果現在遇到的數（index = i） 比前一個數大（index = i-1），就可以開始nums[i] value 減一，nums[i-1] value 加一
* 但這個減一加一的狀況，在兩數平均值時會停止

## 解法

import math # 用來叫 ceil()出來作無條件進位
class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        ans = 0 # 紀錄遍歷當下的最大值，最後要 output
        total_sum = 0 # 用來算平均值用的總和
        for i in range(len(nums)):
            total_sum += nums[i]
            ans = max( ans, math.ceil(total_sum /(i + 1)))
            # 如果換到不能再換之後比 ans 大，ans 就要更新
            # 算無條件進位：整除時nums[i]、nums[i-1] 會一樣大；不能整除時 nums[i] 要比 nums[i-1] 大 1
        return ans

## 補充
* 無條件進位 ceil() 與無條件捨去 floor() 要 import math；如果是四捨五入 round() 字打上去就可以用了
* 如果不使用 ceil()，可以徒手使用 **(total_sum + i)//(i + 1)**
* **為何無條件進位可以這樣展開？**
1. 把 total_sum 視為 a ， i+1 視為 b
2. 無條件進位 a/b，但會有兩個狀況出現：
* a/b 整除，不需進位 **(1)**
* a/b 不能整除，需要進位 **(2)**
3. 未達成進位，勢必要再加個什麼，**我假設要加的東西 z:**
* a/b + z 要維持整除的數，z < 1 才能不進位 **(1)**
* a/b + z要進位， **z > 1 或能讓 a/b 能整除** 才可以進位，但 z > 1 因為上一點已經不可行。 故 z 要讓讓 a/b 能整除 **(2)**：
* 補滿小數的缺，補上的數 = 1 -(a/b - a//b) = 1 - 1/b
* **1 -(a/b - a//b) 解釋：** 1 - 小數部分 = 補上的缺
* **1 - 1/b 解釋：1 - 小數部分** = 補上的缺（只是我這邊把整數先去掉，留小數處理）
4. 得出 z = 1 - 1/b：
* a/b + z = a/b + 1 - 1/b = (a+b-1)/b
* 代回 total_sum、i+1，得出 (total_sum + i)//(i + 1)