Dada una array arr[ ] de tamaño N y un entero p , la tarea es encontrar el valor máximo posible del elemento más a la derecha de la array arr[ ] realizando como máximo k operaciones. En una operación, disminuya arr[i] en p y aumente arr[ i+1] por p .
Ejemplos:
Entrada: N = 4, p = 2, k = 5, arr = {3, 8, 1, 4}
Salida: 8
Explicación:
se puede realizar la siguiente operación para lograr el valor máximo del elemento más a la derecha:
1. disminuir arr[2] en 2 y aumenta arr[3] en 2, arr = {3, 6, 3, 4}
2. Disminuye arr[2] en 2 y aumenta arr[3] en 2, arr = {3, 4, 5, 4}
3. disminuir arr[2] en 2 y aumentar arr[3] en 2, arr = {3, 2, 5, 4}
4. disminuir arr[3] en 2 y aumentar arr[4] en 2, arr = { 3, 2, 3, 6}
5. disminuir arr[3] en 2 y aumentar arr[4] en 2, arr = {3, 2, 1, 8}Por lo tanto, el valor máximo posible del elemento más a la derecha será 8.
Entrada: N = 5, p = 1, k = 2, arr = {1, 2, 3, 4, 5}
Salida: 7
Enfoque ingenuo: este problema se puede resolver de manera ingenua utilizando un enfoque codicioso . siga los pasos a continuación para resolver el problema:
- Ejecute un ciclo while , hasta que k sea mayor que 0.
- Ejecute un bucle for dentro del bucle while , for i en el rango [N-2, 0] .
- Compruebe si arr[i] es mayor que 1 , aumente arr[i+1] en p y disminuya arr[i] en p y rompa el ciclo .
- Disminuya el valor de k en 1.
- Imprimir arr[N-1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <iostream>
using namespace std;
// Function to calculate maximum value of
// Rightmost element
void maxRightmostElement(int N, int k, int p, int arr[]){
// Calculating maximum value of
// Rightmost element
while(k)
{
for(int i=N-2;i>=0;i--)
{
// Checking if arr[i] is operationable
if(arr[i]>= p)
{
// Performing operation of i-th element
arr[i]=arr[i]-p;
arr[i+1]=arr[i+1]+p;
break;
}
}
// Decreasing the value of k by 1
k--;
}
// Printing rightmost element
cout<<arr[N-1]<<endl;
}
// Driver Code
int main() {
// Given Input
int N = 4, p = 2, k = 5, arr[] = {3, 8, 1, 4};
// Function Call
maxRightmostElement(N, k, p, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate maximum value of
// Rightmost element
static int maxRightmostElement(int N, int k, int p,
int arr[])
{
// Calculating maximum value of
// Rightmost element
while (k > 0) {
for (int i = N - 2; i >= 0; i--) {
// Checking if arr[i] is operationable
if (arr[i] >= p)
{
// Performing operation of i-th element
arr[i] = arr[i] - p;
arr[i + 1] = arr[i + 1] + p;
break;
}
}
// Decreasing the value of k by 1
k--;
}
// returning the rightmost element
return arr[N - 1];
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int N = 4, k = 5, p = 2;
int arr[] = { 3, 8, 1, 4 };
// Function Call
System.out.println(
maxRightmostElement(N, k, p, arr));
}
}
// This code is contributed by dwivediyash
Python3
# Python program for the above approach # Function to calculate maximum value of # Rightmost element def maxRightmostElement(N, k, p, arr): # Calculating maximum value of # Rightmost element while(k) : for i in range(N - 2, -1, -1) : # Checking if arr[i] is operationable if(arr[i] >= p) : # Performing operation of i-th element arr[i] = arr[i] - p arr[i + 1] = arr[i + 1] + p break # Decreasing the value of k by 1 k = k - 1 # Printing rightmost element print(arr[N-1]) # Driver Code # Given Input N = 4 p = 2 k = 5 arr = [3, 8, 1, 4] # Function Call maxRightmostElement(N, k, p, arr) # This code is contributed by sanjoy_62.
C#
using System;
public class GFG {
// Function to calculate maximum value of
// Rightmost element
static int maxRightmostElement(int N, int k, int p,
int []arr)
{
// Calculating maximum value of
// Rightmost element
while (k > 0) {
for (int i = N - 2; i >= 0; i--) {
// Checking if arr[i] is operationable
if (arr[i] >= p) {
// Performing operation of i-th element
arr[i] = arr[i] - p;
arr[i + 1] = arr[i + 1] + p;
break;
}
}
// Decreasing the value of k by 1
k--;
}
// returning the rightmost element
return arr[N - 1];
}
// Driver Code
static public void Main()
{
// Given Input
int N = 4, k = 5, p = 2;
int[] arr = { 3, 8, 1, 4 };
// Function Call
Console.WriteLine(
maxRightmostElement(N, k, p, arr));
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate maximum value of
// Rightmost element
function maxRightmostElement(N, k, p, arr) {
// Calculating maximum value of
// Rightmost element
while (k) {
for (let i = N - 2; i >= 0; i--) {
// Checking if arr[i] is operationable
if (arr[i] >= p) {
// Performing operation of i-th element
arr[i] = arr[i] - p;
arr[i + 1] = arr[i + 1] + p;
break;
}
}
// Decreasing the value of k by 1
k--;
}
// Printing rightmost element
document.write(arr[N - 1] + "<br>");
}
// Driver Code
// Given Input
let N = 4, p = 2, k = 5, arr = [3, 8, 1, 4];
// Function Call
maxRightmostElement(N, k, p, arr);
// This code is contributed by Potta Lokesh
</script>
Producción
8
Complejidad temporal: O(N*k)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar al observar el hecho de que el elemento i-ésimo de la array arr[] puede contribuir con 2 al elemento arr[N-1] en las operaciones N-1-i . siga los pasos a continuación para resolver el problema:
- Iterar un ciclo, para i en el rango [N-2, 0].
- Inicialice ans como arr[N-1] para almacenar el valor máximo del elemento más a la derecha .
- Encuentre la contribución mínima del i-ésimo elemento, digamos d como, d = min(a[i]/2, k/(N-1-i)).
- Disminuir k por d*(N-1-i) y aumentar ans por d*2.
- Imprimir ans, será el paso final .
C++
// C++ program for above approach
#include <iostream>
using namespace std;
// Function to calculate maximum value of
// Rightmost element
void maxRightmostElement(int N, int k, int arr[]){
// Initializing ans to store
// Maximum valued rightmost element
int ans = arr[N-1];
// Calculating maximum value of
// Rightmost element
for(int i=N-2; i>=0; i--)
{
int d = min(arr[i]/2, k/(N-1-i));
k-=d*(N-1-i);
ans+=d*2;
}
// Printing rightmost element
cout<<ans<<endl;
}
// Driver Code
int main() {
// Given Input
int N = 4, k = 5, arr[] = {3, 8, 1, 4};
// Function Call
maxRightmostElement(N, k, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate maximum value of
// Rightmost element
static int maxRightmostElement(int N, int k, int p, int arr[])
{
// Initializing ans to store
// Maximum valued rightmost element
int ans = arr[N - 1];
// Calculating maximum value of
// Rightmost element
for (int i = N - 2; i >= 0; i--) {
int d = Math.min(arr[i] / p, k / (N - 1 - i));
k -= d * (N - 1 - i);
ans += d * p;
}
// returning rightmost element
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int N = 4, k = 5, p = 2;
int arr[] = { 3, 8, 1, 4 };
// Function Call
System.out.println(maxRightmostElement(N, k, p, arr));
}
}
// This code is contributed by dwivediyash
Python3
# Python 3 program for above approach # Function to calculate maximum value of # Rightmost element def maxRightmostElement(N, k, arr): # Initializing ans to store # Maximum valued rightmost element ans = arr[N-1] # Calculating maximum value of # Rightmost element i = N - 2 while(i >= 0): d = min(arr[i]//2, k//(N-1-i)) k -= d * (N - 1 - i) ans+=d*2 # Printing rightmost element i -= 1 print(ans,end = " ") # Driver Code if __name__ == '__main__': # Given Input N = 4 k = 5 arr = [3, 8, 1, 4] # Function Call maxRightmostElement(N, k, arr) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG {
// Function to calculate maximum value of
// Rightmost element
static int maxRightmostElement(int N, int k, int p, int []arr)
{
// Initializing ans to store
// Maximum valued rightmost element
int ans = arr[N - 1];
// Calculating maximum value of
// Rightmost element
for (int i = N - 2; i >= 0; i--) {
int d = Math.Min(arr[i] / p, k / (N - 1 - i));
k -= d * (N - 1 - i);
ans += d * p;
}
// returning rightmost element
return ans;
}
// Driver Code
public static void Main(string[] args)
{
// Given Input
int N = 4, k = 5, p = 2;
int []arr = { 3, 8, 1, 4 };
// Function Call
Console.WriteLine(maxRightmostElement(N, k, p, arr));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate maximum value of
// Rightmost element
function maxRightmostElement( N, k, p, arr)
{
// Initializing ans to store
// Maximum valued rightmost element
var ans = arr[N - 1];
// Calculating maximum value of
// Rightmost element
for (var i = N - 2; i >= 0; i--) {
var d = Math.min(arr[i] / p, k / (N - 1 - i));
k -= d * (N - 1 - i);
ans += d * p;
}
// returning rightmost element
return ans;
}
// Driver Code
// Given Input
var N = 4, k = 3.5, p = 2;
var arr = [ 3, 8, 1, 4 ];
// Function Call
document.write(maxRightmostElement(N, k, p, arr));
// This code is contributed by shivanisinghss2110
</script>
Producción
8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dwivediyash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA