Saltar al contenido

Valor máximo que puede obtener en el índice 0 al realizar la operación dada

Mejorar artículo

Guardar artículo

Me gusta el artículo

Mejorar artículo

Guardar artículo

Dada una matriz números[] de tamaño norteEncuentra el máximo valor que puedes lograr en el índice 0 después de ejecutar la operación incrementando el valor en el índice en cada operación 0 en 1 y disminuir el valor en índice i por 1 tal que números[0] < números[i] (1 ≤ yo ≤ N-1). Puede realizar tantos movimientos como desee (posiblemente cero).

Ejemplos:

Aporte: números[] = {1, 2, 3}
Salida: 3
Explicación: números[0] < números[1]Por lo tanto número[0] + 1 y número[1] — 1. Ahora, números[0] = 2, número[0] < números[2], repite el paso de nuevo. ahora numeros[0] se está convirtiendo 3 que es el valor máximo posible que podemos obtener en el índice 0.

Aporte: números[] = {1, 2, 2}
Salida: 2

Acercarse: El problema se puede resolver a partir de la siguiente idea:

Para alcanzar el valor máximo en el índice 0, ordene la matriz desde el índice 1 hasta el último índice y también puede iterar desde el índice 1 y si en algún momento nums[i] resulta ser mayor que el elemento presente en el índice 0, de acuerdo con los números de edición dados[0] obtener planteado y nums[i] ser reducido. Entonces, números[0] incrementarse en la cantidad (números[i] – números[0] + 1) / 2 cuando encuentran un valor mayor.

Siga los pasos a continuación para implementar la idea:

  • Almacene el valor inicial presente en el índice 0 en una variable.
  • Ordene la matriz desde el índice 1 hasta el último índice.
  • Repita desde el índice 1 y si lo encuentra números[i] > numeros[0]realizar la operación dada
  • El valor en el índice obtendrá 0 aumentó Por el (números[i] – números[0] +1) / 2
  • Devuelve el valor en el índice 0 como la respuesta solicitada.

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

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int maximumValue(vector<int>& nums, int n)

{

    

    int value_at_index_0 = nums[0];

 

    

    

    sort(nums.begin() + 1, nums.end());

 

    

    for (int i = 1; i < n; i++) {

 

        

        

        

        if (nums[i] > value_at_index_0) {

 

            

            value_at_index_0

                += (nums[i] - value_at_index_0 + 1) / 2;

        }

    }

 

    

    return value_at_index_0;

}

 

int main()

{

    vector<int> nums = { 1, 2, 3 };

    int N = nums.size();

 

    

    cout << maximumValue(nums, N);

 

    return 0;

}

Complejidad del tiempo: O(N * registro N)
cuarto auxiliar: O(1)

Artículos relacionados: