Número máximo de cubos que se pueden llenar

Dada una array arr[] que consta de capacidades de N cubos, donde arr[i] denota la capacidad del i ^-ésimo cubo. Si la cantidad total de agua disponible es la suma de los índices de array ( indexación basada en 1 ), la tarea es encontrar la cantidad máxima de baldes que se pueden llenar con el agua disponible. El balde se considerará lleno si contiene al menos 1 litro.
 

Ejemplos:

Entrada: arr[] = {1, 5, 3, 4, 7, 9}
Salida: 4
Explicación:
Total de agua disponible = Suma de los índices de array de arr[] = 1 + 2 + 3 + 4 + 5 = 15.
Ordenar los array en orden ascendente modifica la array a {1, 3, 4, 5, 7, 9}.
Llene el balde con capacidad 1, luego . Ahora, agua disponible = 14. 
Llena el balde con capacidad 3 . Ahora, agua disponible = 11.
Llenar balde con capacidad 4. Ahora, agua disponible = 7.
Llenar balde con capacidad 5. Ahora, agua disponible = 2. En este caso se llena con más de 1 litro por lo que también se considera este balde .
Por lo tanto, el total de baldes que se pueden llenar por completo con agua es 4.

Entrada: arr[] = {2, 5, 8, 3, 2, 10, 8}
Salida: 5

Enfoque: El problema dado se puede resolver con avaricia . Siga los pasos a continuación para resolver el problema dado:

• Calcule la disponibilidad total de agua calculando la suma de los primeros N números naturales .
• Ordene la array arr[] en orden ascendente .
• Recorra la array dada arr[] y encuentre la suma de los elementos de la array hasta ese índice, digamos i , donde la suma excede la disponibilidad total.
• Después de completar los pasos anteriores, imprima el valor del índice i como el número máximo de cubos que se pueden llenar.

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 find the maximum number
// of buckets that can be filled with
// the amount of water available
int getBuckets(int arr[], int N)
{
    // Find the total available water
    int availableWater = N * (N - 1) / 2;
 
    // Sort the array in ascending order
    sort(arr, arr + N);
 
    int i = 0, sum = 0;
 
    // Check if bucket can be
    // filled with available water
    while (sum <= availableWater) {
        sum += arr[i];
        i++;
    }
 
    // Print count of buckets
    cout << i - 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 3, 4, 7, 9 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    getBuckets(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
   
  // Function to find the maximum number
  // of buckets that can be filled with
  // the amount of water available
  static void getBuckets(int[] arr, int N)
  {
    // Find the total available water
    int availableWater = N * (N - 1) / 2;
 
    // Sort the array in ascending order
    Arrays.sort(arr);
 
    int i = 0, sum = 0;
 
    // Check if bucket can be
    // filled with available water
    while (sum <= availableWater) {
      sum += arr[i];
      i++;
    }
 
    // Print count of buckets
    System.out.println(i - 1);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[] arr = { 1, 5, 3, 4, 7, 9 };
    int N = arr.length;
 
    getBuckets(arr, N);
  }
}
 
// This code is contributed by divyesh072019.

# Python3 program for the above approach
 
# Function to find the maximum number
# of buckets that can be filled with
# the amount of water available
def getBuckets(arr, N) :
 
    # Find the total available water
    availableWater = N * (N - 1) // 2
 
    # Sort the array in ascending order
    arr.sort()
 
    i, Sum = 0, 0
 
    # Check if bucket can be
    # filled with available water
    while (Sum <= availableWater) :
        Sum += arr[i]
        i += 1
 
    # Print count of buckets
    print(i - 1, end = "")
 
arr = [ 1, 5, 3, 4, 7, 9 ]
N = len(arr)
 
getBuckets(arr, N);
 
# This code is contributed by divyeshrabadiya07.

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
   
  // Function to find the maximum number
  // of buckets that can be filled with
  // the amount of water available
  static void getBuckets(int[] arr, int N)
  {
     
    // Find the total available water
    int availableWater = N * (N - 1) / 2;
 
    // Sort the array in ascending order
    Array.Sort(arr);
    int i = 0, sum = 0;
 
    // Check if bucket can be
    // filled with available water
    while (sum <= availableWater)
    {
      sum += arr[i];
      i++;
    }
 
    // Print count of buckets
    Console.Write(i - 1);
  }
 
// Driver Code
public static void Main(String[] args)
{
    int[] arr = { 1, 5, 3, 4, 7, 9 };
    int N = arr.Length;
 
    getBuckets(arr, N);
}
}
 
// This code is contributed by splevel62.

<script>
 
    // Javascript program to implement
    // the above approach
     
    // Function to find the maximum number
    // of buckets that can be filled with
    // the amount of water available
    function getBuckets(arr, N)
    {
 
      // Find the total available water
      let availableWater = N * (N - 1) / 2;
 
      // Sort the array in ascending order
      arr.sort(function(a, b){return a - b});
      let i = 0, sum = 0;
 
      // Check if bucket can be
      // filled with available water
      while (sum <= availableWater)
      {
        sum += arr[i];
        i++;
      }
 
      // Print count of buckets
      document.write(i - 1);
    }
     
    let arr = [ 1, 5, 3, 4, 7, 9 ];
    let N = arr.length;
  
    getBuckets(arr, N);
   
</script>

4

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)