Maximice el elemento en el índice K en una array con una suma M como máximo y una diferencia entre elementos adyacentes como máximo 1

Dado un entero positivo N , la tarea es construir una array de longitud N y encontrar el valor máximo en el índice K de modo que la suma de todos los elementos de la array sea como máximo M y la diferencia absoluta entre dos elementos consecutivos de la array sea de la mayoría 1 .

Ejemplos:

Entrada: N = 3, M = 7, K = 1
Salida: 3
Explicación: 
De acuerdo con las restricciones dadas, la array con valores {2, 3, 2} maximiza el valor en el índice 1. Por lo tanto, la salida requerida es 3.

Entrada: N = 3, M = 8, K = 1
Salida: 3

Enfoque: la idea es lograr el valor máximo en el índice K y disminuir la suma de otros elementos para cumplir con el criterio de que la suma de la array sea M como máximo . Siga los pasos a continuación:

• Sea X el valor en el índice K. Entonces el elemento en K – 1 es X – 1 , en K – 2 es X – 2 y así sucesivamente.
• En el índice 0 el valor es X – K. De manera similar, en el índice K + 1 el valor es X – 1 y así sucesivamente hasta X – (N – K – 1) en el índice N – 1 .
• Entonces, para lograr el valor máximo en el índice K , la estructura de la array sería X – K, X – (K – 1), …., X – 2, X – 1, X, X – 1, X – 2, …. ., X – (N – K – 1) .
• Entonces, después de arreglar la ecuación, se convierte en K * X – (1 + 2 + …. + K) + X + (N – K – 1) * X – (1 + 2 + …. + (N – K – 1) ) ≤ METRO .

Sigue los pasos para resolver la ecuación anterior:

• Calcular (1 + 2 + …. + K) usando K * (K + 1) / 2 y (1 + 2 + ….. + (N – K – 1)) usando (N – K – 1) * (N – K) / 2 y almacenar en S1 y S2 respectivamente.
• Esto reduce la ecuación a X * (K + 1 + N – K – 1) ≤ M + S1 + S2 .
• Ahora, el valor máximo de X se puede obtener calculando (M + S1 + S2) / N.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the maximum
// possible value at index K
void maxValueAtIndexK(int N, int K, int M)
{
    // Stores the sum of elements
    // in the left and right of index K
    int S1 = 0, S2 = 0;
 
    S1 = K * (K + 1) / 2;
    S2 = (N - K - 1) * (N - K) / 2;
 
    // Stores the maximum
    // possible value at index K
    int X = (M + S1 + S2) / N;
 
    // Print the answer
    cout << X;
}
 
// Driver Code
int main()
{
    // Given N, K & M
    int N = 3, K = 1, M = 7;
    maxValueAtIndexK(N, K, M);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to calculate the maximum
// possible value at index K
static void maxValueAtIndexK(int N, int K,
                             int M)
{
     
    // Stores the sum of elements
    // in the left and right of index K
    int S1 = 0, S2 = 0;
 
    S1 = K * (K + 1) / 2;
    S2 = (N - K - 1) * (N - K) / 2;
 
    // Stores the maximum
    // possible value at index K
    int X = (M + S1 + S2) / N;
 
    // Print the answer
    System.out.println(X);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N, K & M
    int N = 3, K = 1, M = 7;
     
    maxValueAtIndexK(N, K, M);
}
}
 
// This code is contributed by Dharanendra L V

# Python program for the above approach
 
# Function to calculate the maximum
# possible value at index K
def maxValueAtIndexK(N, K, M):
 
    # Stores the sum of elements
    # in the left and right of index K
    S1 = 0; S2 = 0;
    S1 = K * (K + 1) // 2;
    S2 = (N - K - 1) * (N - K) // 2;
 
    # Stores the maximum
    # possible value at index K
    X = (M + S1 + S2) // N;
 
    # Print the answer
    print(X);
 
# Driver Code
if __name__ == '__main__':
 
    # Given N, K & M
    N = 3; K = 1; M = 7;
    maxValueAtIndexK(N, K, M);
 
# This code is contributed by 29AjayKumar

// C# program for the above approach
using System;
 
class GFG{
 
// Function to calculate the maximum
// possible value at index K
static void maxValueAtIndexK(int N, int K,
                             int M)
{
     
    // Stores the sum of elements
    // in the left and right of index K
    int S1 = 0, S2 = 0;
 
    S1 = K * (K + 1) / 2;
    S2 = (N - K - 1) * (N - K) / 2;
 
    // Stores the maximum
    // possible value at index K
    int X = (M + S1 + S2) / N;
 
    // Print the answer
    Console.WriteLine(X);
}
 
// Driver Code
static public void Main()
{
     
    // Given N, K & M
    int N = 3, K = 1, M = 7;
     
    maxValueAtIndexK(N, K, M);
}
}
 
// This code is contributed by Dharanendra L V

<script>
// JavaScript program for
// the above approach
  
// Function to calculate the maximum
// possible value at index K
function maxValueAtIndexK(N, K, M)
{
    // Stores the sum of elements
    // in the left and right of index K
    let S1 = 0, S2 = 0;
 
    S1 = K * (K + 1) / 2;
    S2 = (N - K - 1) * (N - K) / 2;
 
    // Stores the maximum
    // possible value at index K
    let X = (M + S1 + S2) / N;
 
    // Print the answer
     document.write(X);
}
 
// Driver Code
  
    // Given N, K & M
    let N = 3, K = 1, M = 7;
    maxValueAtIndexK(N, K, M);
  
</script>

3

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)