摘要
Title: 2439. 最小化数组中的最大值
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms

2439. 最小化数组中的最大值

ps: 忙于考研，等考完再日更

题意

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。
每一步操作中，你需要：
选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
将 nums[i] 减 1 。
将 nums[i - 1] 加 1 。
你可以对数组执行任意次上述操作，请你返回可以得到的 nums 数组中最大值最小为多少。
思路

求最大值最小为多少，很容易想到二分的思路，二分到最小的符合的
check函数，根据题目描述，就是数组前面的相对小的数，可以承载后面的数变成mid的消耗，动态遍历即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-10-24 15:17:09
* @FilePath: \LeetCode\2439\2439.cpp
* @LastEditTime: 2022-10-24 15:38:07
*/
#include <bits/stdc++.h>
using namespace std;

// ---------------------
#define N n + 100
#define SZ(X) ((int)(X).size())
#define DEBUG(X) cout << #X << ": " << X << '\n'
#define LL long long
typedef pair<int, int> PII;

// #undef N
// const int N = 1e5 + 10;

static int IOS = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution
{
  public:
    int minimizeArrayValue(vector<int> &nums)
    {
        LL l = 0, r = *max_element(nums.begin(), nums.end());

        auto check = [&](int x) {
            LL sum = 0; // 可承载量
            for (auto num : nums)
            {
                if (num < x)
                    sum += x - num;
                else
                {
                    if (sum < num - x)
                        return false;
                    sum -= num - x;
                }
            }
            return true;
        };

        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

// ---------------------

// signed main()
// {
//     Solution solution;
//     vector<int> a = {3, 7, 1, 6};
//     solution.minimizeArrayValue(a);
//     return 0;
// }

2439. 最小化数组中的最大值

题意

思路

代码