Maximice el elemento de array más pequeño incrementando todos los elementos en un subarreglo de longitud K en 1 exactamente M veces

Dada una array arr[] de tamaño N y los números enteros M y K , la tarea es encontrar el valor máximo posible del elemento de array más pequeño realizando M operaciones. En cada operación, aumente el valor de todos los elementos en un subarreglo contiguo de longitud K en 1 .

Ejemplos:

Entrada: arr[ ] = {2, 2, 2, 2, 1, 1}, M = 1, K = 3
Salida: 2
Explicación: actualice los últimos 3 elementos en el primer movimiento, luego la array actualizada es [2, 2, 2, 3, 2, 2]. El elemento más pequeño tiene un valor de 2.

Entrada: arr[ ] = {5, 8}, M = 5, K = 1
Salida: 9

Enfoque: el problema se puede resolver utilizando la búsqueda binaria . Recorra la array arr[] y para cada elemento arr[i] , cuente el número de operaciones requeridas. Si se requiere que el elemento actual se actualice x veces, agregue x a la respuesta y actualice el segmento consecutivo de longitud K x veces .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, k, l, r, i;
 
// Function to check if the smallest
// value of v is achievable or not
ll check(ll v, vector<ll>& a)
{
    ll tec = 0, ans = 0;
 
    // Create array to
    // store previous moves
    vector<ll> b(n + k + 1);
 
    for (i = 0; i < n; i++) {
 
        // Remove previous moves
        tec -= b[i];
 
        if (a[i] + tec < v) {
 
            // Add balance to ans
            ll mov = v - a[i] - tec;
            ans = ans + mov;
 
            // Update contiguous
            // subarray of length k
            tec += mov;
            b[i + k] = mov;
        }
    }
 
    // Number of moves
    // should not exceed m
    return (ans <= m);
}
 
// Function to find the maximum
// value of the smallest array
// element that can be obtained
ll FindLargest(vector<ll> a)
{
    l = 1;
    r = pow(10, 10);
 
    // Perform Binary search
    while (r - l > 0) {
 
        ll tm = (l + r + 1) / 2;
 
        if (check(tm, a))
            l = tm;
        else
            r = tm - 1;
    }
    return l;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<ll> a{ 2, 2, 2, 2, 1, 1 };
    m = 2;
    k = 3;
    n = a.size();
 
    // Function Call
    cout << FindLargest(a);
    return 0;
}

// Java program for above approach
class GFG{
     
static long n, m, k, l, r, i;
 
// Function to check if the smallest
// value of v is achievable or not
static boolean check(long v, long[] a)
{
    long tec = 0, ans = 0;
     
    // Create array to
    // store previous moves
    long[] b = new long[(int)(n + k + 1)];
 
    for(int i = 0; i < n; i++)
    {
         
        // Remove previous moves
        tec -= b[i];
 
        if (a[i] + tec < v)
        {
             
            // Add balance to ans
            long mov = v - a[i] - tec;
            ans = ans + mov;
 
            // Update contiguous
            // subarray of length k
            tec += mov;
            b[i + (int)k] = mov;
        }
    }
 
    // Number of moves
    // should not exceed m
    return ans <= m;
}
 
// Function to find the maximum
// value of the smallest array
// element that can be obtained
static long FindLargest(long[] a)
{
    l = 1;
    r = (long)Math.pow(10, 10);
 
    // Perform Binary search
    while (r - l > 0)
    {
        long tm = (l + r + 1) / 2;
 
        if (check(tm, a))
            l = tm;
        else
            r = tm - 1;
    }
    return l;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Input
    long[] a = { 2, 2, 2, 2, 1, 1 };
    m = 2;
    k = 3;
    n = a.length;
 
    // Function Call
    System.out.println(FindLargest(a));
}
}
 
// This code is contributed by hritikrommie.

# Python 3 program for above approach
 
n = 0
m = 0
k = 0
l = 0
r = 0
i = 0
 
from math import pow
# Function to check if the smallest
# value of v is achievable or not
def check(v, a):
    tec = 0
    ans = 0
 
    # Create array to
    # store previous moves
    b = [0 for i in range(n + k + 1)]
 
    for i in range(n):
        # Remove previous moves
        tec -= b[i]
 
        if (a[i] + tec < v):
            # Add balance to ans
            mov = v - a[i] - tec
            ans = ans + mov
 
            # Update contiguous
            # subarray of length k
            tec += mov
            b[i + k] = mov
 
    # Number of moves
    # should not exceed m
    return (ans <= m)
 
# Function to find the maximum
# value of the smallest array
# element that can be obtained
def FindLargest(a):
    l = 1
    r = pow(10, 10)
 
    # Perform Binary search
    while (r - l > 0):
        tm = (l + r + 1) // 2
 
        if (check(tm, a)):
            l = tm
        else:
            r = tm - 1
    return l
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    a = [2, 2, 2, 2, 1, 1]
    m = 2
    k = 3
    n = len(a)
 
    # Function Call
    print(int(FindLargest(a)))
     
    # This code is contributed by ipg2016107.

// C# program for above approach
using System;
 
public class GFG
{
     
static long n, m, k, l, r, i;
 
// Function to check if the smallest
// value of v is achievable or not
static bool check(long v, long[] a)
{
    long tec = 0, ans = 0;
     
    // Create array to
    // store previous moves
    long[] b = new long[(int)(n + k + 1)];
 
    for(int i = 0; i < n; i++)
    {
         
        // Remove previous moves
        tec -= b[i];
 
        if (a[i] + tec < v)
        {
             
            // Add balance to ans
            long mov = v - a[i] - tec;
            ans = ans + mov;
 
            // Update contiguous
            // subarray of length k
            tec += mov;
            b[i + (int)k] = mov;
        }
    }
 
    // Number of moves
    // should not exceed m
    return ans <= m;
}
 
// Function to find the maximum
// value of the smallest array
// element that can be obtained
static long FindLargest(long[] a)
{
    l = 1;
    r = (long)Math.Pow(10, 10);
 
    // Perform Binary search
    while (r - l > 0)
    {
        long tm = (l + r + 1) / 2;
 
        if (check(tm, a))
            l = tm;
        else
            r = tm - 1;
    }
    return l;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given Input
    long[] a = { 2, 2, 2, 2, 1, 1 };
    m = 2;
    k = 3;
    n = a.Length;
 
    // Function Call
    Console.WriteLine(FindLargest(a));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for above approach
let n = 0, m = 0, k = 0, l = 0, r = 0, i = 0;
 
// Function to check if the smallest
// value of v is achievable or not
function check(v, a)
{
    let tec = 0,
    ans = 0;
     
    // Create array to
    // store previous moves
    let b = new Array(n + k + 1).fill(0);
     
    for(i = 0; i < n; i++)
    {
         
        // Remove previous moves
        tec -= b[i];
         
        if (a[i] + tec < v)
        {
             
            // Add balance to ans
            let mov = v - a[i] - tec;
            ans = ans + mov;
             
            // Update contiguous
            // subarray of length k
            tec += mov;
            b[i + k] = mov;
        }
    }
     
    // Number of moves
    // should not exceed m
    return ans <= m;
}
 
// Function to find the maximum
// value of the smallest array
// element that can be obtained
function FindLargest(a)
{
    l = 1;
    r = Math.pow(10, 10);
     
    // Perform Binary search
    while (r - l > 0)
    {
        let tm = Math.floor((l + r + 1) / 2);
         
        if (check(tm, a)) l = tm;
        else r = tm - 1;
    }
    return l;
}
 
// Driver Code
 
// Given Input
let a = [ 2, 2, 2, 2, 1, 1 ];
m = 2;
k = 3;
n = a.length;
 
// Function Call
document.write(FindLargest(a));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

2

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N + K)