GeeksforGeeks-Solution/src/Max min Height/Code/solution.cpp at main · withaarzoo/GeeksforGeeks-Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution
{
public:
    bool canMake(vector<int> &arr, int n, int k, int w, long long target)
    {
        vector<long long> diff(n + 1, 0);
        long long currAdd = 0;
        long long operations = 0;

        for (int i = 0; i < n; i++)
        {
            currAdd += diff[i];

            long long currentHeight = arr[i] + currAdd;

            if (currentHeight < target)
            {
                long long need = target - currentHeight;
                operations += need;
                if (operations > k)
                    return false;

                currAdd += need;
                if (i + w < n)
                    diff[i + w] -= need;
            }
        }
        return true;
    }

    int maxMinHeight(vector<int> &arr, int k, int w)
    {
        int n = arr.size();
        int minVal = *min_element(arr.begin(), arr.end());

        long long low = minVal;
        long long high = minVal + k;
        long long ans = minVal;

        while (low <= high)
        {
            long long mid = (low + high) / 2;

            if (canMake(arr, n, k, w, mid))
            {
                ans = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        return (int)ans;
    }
};