Dados tres números N , K y M , la tarea es encontrar el valor máximo que se puede asignar al índice K-ésimo si se asignan valores positivos a todos los N índices de manera que la suma total de valores sea menor que M y la diferencia entre los valores en posiciones adyacentes es como máximo 1.
Ejemplos:
Entrada : N=3, M=10, K=2
Salida : 4
Explicación : la forma óptima de asignar valores es {3, 4, 3}. Suma total=3+4+3=10≤M.
Nota: {3, 4, 2} no es una distribución válida ya que 4-2=2>1Entrada : N=7, M=100, K=6
Salida : 16
Enfoque: Las siguientes observaciones ayudan a resolver el problema:
- Si se asigna X en el índice K-ésimo , entonces, la distribución óptima es la siguiente:
- Si X es menor que K-1 , la distribución óptima a la izquierda sería (X-1), (X-2), …(X-K+1), (1), (1)…
- En caso contrario sería (X-1), (X-2),…(X-K+1) .
- Si X es menor que NK , la distribución óptima a la izquierda sería (X-1), (X-2), …(X-N+K), 1, 1…
- De lo contrario sería (X-1), (X-2),…(X-N+K) .
- Usando la serie AP , la suma de (X-1)+(X-2)+(X-3)+…+(XY) es Y*(X-1+XY)/2 = Y*(2X-Y -1)/2
El valor máximo de X se puede calcular con el concepto de búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable ans a -1 , para almacenar la respuesta.
- Inicialice dos variables low a 0 y high a M , con el fin de realizar búsquedas binarias.
- Haga un bucle mientras el nivel bajo no sea mayor que el alto y haga lo siguiente:
- Calcula mid como la media de high y low .
- Inicialice una variable val a 0 para almacenar la suma actual de la distribución.
- Inicialice L (número de índices a la izquierda de K ) como K-1 y R (número de índices a la derecha de K ) como NK .
- Agregue el valor de mid a val .
- Distribuya números a la izquierda y derecha de K como se explicó anteriormente y agregue sus valores a val .
- Si val es menor que M , actualice ans como el máximo de ans y mid . Actualizar bajo como mid+1 .
- De lo contrario, actualice alto como mid-1 .
- Regresar respuesta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum value that can be placed at
// the Kth index in a distribution in which difference of
// adjacent elements is less than 1 and total sum of
// distribution is M.
int calculateMax(int N, int M, int K)
{
// variable to store final answer
int ans = -1;
// variables for binary search
int low = 0, high = M;
// Binary search
while (low <= high) {
// variable for binary search
int mid = (low + high) / 2;
// variable to store total sum of array
int val = 0;
// number of indices on the left excluding the Kth
// index
int L = K - 1;
// number of indices on the left excluding the Kth
// index
int R = N - K;
// add mid to final sum
val += mid;
// distribution on left side is possible
if (mid >= L) {
// sum of distribution on the left side
val += (L) * (2 * mid - L - 1) / 2;
}
else {
// sum of distribution on the left side with
// (L-mid) 1s
val += mid * (mid - 1) / 2 + (L - mid);
}
// distribution on right side is possible
if (mid >= R) {
// sum of distribution on the right side
val += (R) * (2 * mid - R - 1) / 2;
}
else {
// sum of distribution on the left side with
// (R-mid) 1s
val += mid * (mid - 1) / 2 + (R - mid);
}
// Distribution is valid
if (val <= M) {
ans = max(ans, mid);
low = mid + 1;
}
else
high = mid - 1;
}
// return answer
return ans;
}
// Driver code
int main()
{
// Input
int N = 7, M = 100, K = 6;
// Function call
cout << calculateMax(N, M, K) << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to calculate maximum value that can be
// placed at
// the Kth index in a distribution in which difference
// of adjacent elements is less than 1 and total sum of
// distribution is M.
public static int calculateMax(int N, int M, int K)
{
// variable to store final answer
int ans = -1;
// variables for binary search
int low = 0, high = M;
// Binary search
while (low <= high)
{
// variable for binary search
int mid = (low + high) / 2;
// variable to store total sum of array
int val = 0;
// number of indices on the left excluding the
// Kth index
int L = K - 1;
// number of indices on the left excluding the
// Kth index
int R = N - K;
// add mid to final sum
val += mid;
// distribution on left side is possible
if (mid >= L)
{
// sum of distribution on the left side
val += (L) * (2 * mid - L - 1) / 2;
}
else
{
// sum of distribution on the left side with
// (L-mid) 1s
val += mid * (mid - 1) / 2 + (L - mid);
}
// distribution on right side is possible
if (mid >= R)
{
// sum of distribution on the right side
val += (R) * (2 * mid - R - 1) / 2;
}
else
{
// sum of distribution on the left side with
// (R-mid) 1s
val += mid * (mid - 1) / 2 + (R - mid);
}
// Distribution is valid
if (val <= M) {
ans = Math.max(ans, mid);
low = mid + 1;
}
else
high = mid - 1;
}
// return answer
return ans;
}
// Driver code
public static void main(String[] args)
{
// Input
int N = 7, M = 100, K = 6;
// Function call
System.out.println(calculateMax(N, M, K));
}
}
// This code is contributed by lokeshpotta20.
Python3
# Python3 program for the above approach # Function to calculate maximum value # that can be placed at the Kth index # in a distribution in which difference # of adjacent elements is less than 1 # and total sum of distribution is M. def calculateMax(N, M, K): # Variable to store final answer ans = -1 # Variables for binary search low = 0 high = M # Binary search while (low <= high): # Variable for binary search mid = (low + high) / 2 # Variable to store total sum of array val = 0 # Number of indices on the left excluding # the Kth index L = K - 1 # Number of indices on the left excluding # the Kth index R = N - K # Add mid to final sum val += mid # Distribution on left side is possible if (mid >= L): # Sum of distribution on the left side val += (L) * (2 * mid - L - 1) / 2 else: # Sum of distribution on the left side # with (L-mid) 1s val += mid * (mid - 1) / 2 + (L - mid) # Distribution on right side is possible if (mid >= R): # Sum of distribution on the right side val += (R) * (2 * mid - R - 1) / 2 else: # Sum of distribution on the left side with # (R-mid) 1s val += mid * (mid - 1) / 2 + (R - mid) # Distribution is valid if (val <= M): ans = max(ans, mid) low = mid + 1 else: high = mid - 1 # Return answer return int(ans) # Driver code # Input N = 7 M = 100 K = 6 # Function call print(calculateMax(N, M, K)); # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG
{
// Function to calculate maximum value that can be
// placed at
// the Kth index in a distribution in which difference
// of adjacent elements is less than 1 and total sum of
// distribution is M.
public static int calculateMax(int N, int M, int K)
{
// variable to store final answer
int ans = -1;
// variables for binary search
int low = 0, high = M;
// Binary search
while (low <= high)
{
// variable for binary search
int mid = (low + high) / 2;
// variable to store total sum of array
int val = 0;
// number of indices on the left excluding the
// Kth index
int L = K - 1;
// number of indices on the left excluding the
// Kth index
int R = N - K;
// add mid to final sum
val += mid;
// distribution on left side is possible
if (mid >= L)
{
// sum of distribution on the left side
val += (L) * (2 * mid - L - 1) / 2;
}
else
{
// sum of distribution on the left side with
// (L-mid) 1s
val += mid * (mid - 1) / 2 + (L - mid);
}
// distribution on right side is possible
if (mid >= R)
{
// sum of distribution on the right side
val += (R) * (2 * mid - R - 1) / 2;
}
else
{
// sum of distribution on the left side with
// (R-mid) 1s
val += mid * (mid - 1) / 2 + (R - mid);
}
// Distribution is valid
if (val <= M) {
ans = Math.Max(ans, mid);
low = mid + 1;
}
else
high = mid - 1;
}
// return answer
return ans;
}
// Driver code
static void Main()
{
// Input
int N = 7, M = 100, K = 6;
// Function call
Console.Write(calculateMax(N, M, K));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate maximum value that can be placed at
// the Kth index in a distribution in which difference of
// adjacent elements is less than 1 and total sum of
// distribution is M.
function calculateMax(N, M, K)
{
// variable to store final answer
var ans = -1;
// variables for binary search
var low = 0, high = M;
// Binary search
while (low <= high)
{
// variable for binary search
var mid = parseInt((low + high) / 2);
// variable to store total sum of array
var val = 0;
// number of indices on the left excluding the Kth
// index
var L = K - 1;
// number of indices on the left excluding the Kth
// index
var R = N - K;
// add mid to final sum
val += mid;
// distribution on left side is possible
if (mid >= L)
{
// sum of distribution on the left side
val += (L) * ((2 * mid - L - 1) / 2);
}
else
{
// sum of distribution on the left side with
// (L-mid) 1s
val += mid * parseInt((mid - 1) / 2) + (L - mid);
}
// distribution on right side is possible
if (mid >= R)
{
// sum of distribution on the right side
val += (R) * (2 * mid - R - 1) / 2;
}
else
{
// sum of distribution on the left side with
// (R-mid) 1s
val += mid * parseInt((mid - 1) / 2) + (R - mid);
}
// Distribution is valid
if (val <= M)
{
ans = Math.max(ans, mid);
low = mid + 1;
}
else
high = mid - 1;
}
// return answer
return ans;
}
// Driver code
// Input
let N = 7, M = 100, K = 6;
// Function call
document.write(calculateMax(N, M, K));
// This code is contributed by lokeshpotta20.
</script>
Producción
16
Complejidad de Tiempo: O(LogM)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por samarpitsmarty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA