Dada una array arr que contiene N valores que describen la prioridad de N trabajos. La tarea es formar conjuntos de cuatrillizos (W, X, Y, Z) que se realizarán cada día de manera que W >= X >= Y >= Z y, al hacerlo, maximizar la suma de todos los Y en todos los conjuntos de cuatrillizos.
Nota : N siempre será múltiplo de 4.
Ejemplos:
Entrada: Arr[] = {2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2}
Salida: 10
Explicación:
Podemos formar 3 conjuntos cuádruples como [7, 5, 5, 1], [4, 3, 3, 1], [2, 2, 2, 1].
La suma de todas las Y es 5 + 3 + 2 = 10 que es el valor máximo posible.
Entrada: arr[] = {1, 51, 91, 1, 1, 16, 1, 51, 48, 16, 1, 49}
Salida: 68
Planteamiento: Para resolver el problema antes mencionado podemos observar que:
- Independientemente de Y, (W, X) >= Y, es decir, los valores más altos de W y X siempre se pierden y no contribuyen a la respuesta. Por lo tanto, debemos mantener estos valores lo más bajos posible pero mayores o iguales a Y.
- De manera similar, el valor de Z siempre se pierde y debe ser menor que Y. Por lo tanto, debe ser lo más bajo posible.
Por lo tanto, para satisfacer la condición anterior tenemos que:
- primero ordena la array dada en orden descendente .
- inicialice un puntero que apunte al tercer elemento de cada par desde el índice 0.
- reste el recuento de dichos pares del tamaño de la array, es decir, N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to Maximize 3rd element
// sum in quadruplet sets formed
// from given Array
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// possible value of Y
int formQuadruplets(int arr[], int n)
{
int ans = 0, pairs = 0;
// pairs contain count
// of minimum elements
// that will be utilized
// at place of Z.
// it is equal to count of
// possible pairs that
// is size of array divided by 4
pairs = n / 4;
// sorting the array in descending order
// so as to bring values with minimal
// difference closer to arr[i]
sort(arr, arr + n, greater<int>());
for (int i = 0; i < n - pairs; i += 3) {
// here, i+2 acts as a
// pointer that points
// to the third value of
// every possible quadruplet
ans += arr[i + 2];
}
// returning the optimally
// maximum possible value
return ans;
}
// Driver code
int main()
{
// array declaration
int arr[] = { 2, 1, 7, 5, 5,
4, 1, 1, 3, 3,
2, 2 };
// size of array
int n = sizeof(arr) / sizeof(arr[0]);
cout << formQuadruplets(arr, n)
<< endl;
return 0;
}
Java
// Java code to Maximize 3rd element
// sum in quadruplet sets formed
// from given Array
import java.util.*;
class GFG{
// Function to find the maximum
// possible value of Y
static int formQuadruplets(Integer arr[], int n)
{
int ans = 0, pairs = 0;
// pairs contain count
// of minimum elements
// that will be utilized
// at place of Z.
// it is equal to count of
// possible pairs that
// is size of array divided by 4
pairs = n / 4;
// sorting the array in descending order
// so as to bring values with minimal
// difference closer to arr[i]
Arrays.sort(arr, Collections.reverseOrder());
for (int i = 0; i < n - pairs; i += 3)
{
// here, i+2 acts as a
// pointer that points
// to the third value of
// every possible quadruplet
ans += arr[i + 2];
}
// returning the optimally
// maximum possible value
return ans;
}
// Driver code
public static void main(String[] args)
{
// array declaration
Integer arr[] = { 2, 1, 7, 5, 5, 4,
1, 1, 3, 3, 2, 2 };
// size of array
int n = arr.length;
System.out.print(
formQuadruplets(arr, n) + "\n");
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 code to maximize 3rd element # sum in quadruplet sets formed # from given Array # Function to find the maximum # possible value of Y def formQuadruplets(arr, n): ans = 0 pairs = 0 # Pairs contain count of minimum # elements that will be utilized # at place of Z. It is equal to # count of possible pairs that # is size of array divided by 4 pairs = n // 4 # Sorting the array in descending order # so as to bring values with minimal # difference closer to arr[i] arr.sort(reverse = True) for i in range(0, n - pairs, 3): # Here, i+2 acts as a pointer that # points to the third value of # every possible quadruplet ans += arr[i + 2] # Returning the optimally # maximum possible value return ans # Driver code # Array declaration arr = [ 2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2 ] # Size of array n = len(arr) print(formQuadruplets(arr, n)) # This code is contributed by divyamohan123
C#
// C# code to maximize 3rd element
// sum in quadruplet sets formed
// from given Array
using System;
class GFG{
// Function to find the maximum
// possible value of Y
static int formQuadruplets(int []arr, int n)
{
int ans = 0, pairs = 0;
// Pairs contain count of minimum
// elements that will be utilized at
// place of Z. It is equal to count of
// possible pairs that is size of
// array divided by 4
pairs = n / 4;
// Sorting the array in descending order
// so as to bring values with minimal
// difference closer to arr[i]
Array.Sort(arr);
Array.Reverse(arr);
for(int i = 0; i < n - pairs; i += 3)
{
// Here, i+2 acts as a
// pointer that points
// to the third value of
// every possible quadruplet
ans += arr[i + 2];
}
// Returning the optimally
// maximum possible value
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Array declaration
int []arr = { 2, 1, 7, 5, 5, 4,
1, 1, 3, 3, 2, 2 };
// Size of array
int n = arr.Length;
Console.Write(formQuadruplets(arr, n) + "\n");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript code to maximize 3rd element
// sum in quadruplet sets formed
// from given Array
// Function to find the maximum
// possible value of Y
function formQuadruplets(arr, n) {
var ans = 0,
pairs = 0;
// Pairs contain count of minimum
// elements that will be utilized at
// place of Z. It is equal to count of
// possible pairs that is size of
// array divided by 4
pairs = parseInt(n / 4);
// Sorting the array in descending order
// so as to bring values with minimal
// difference closer to arr[i]
arr.sort().reverse();
for (var i = 0; i < n - pairs; i += 3) {
// Here, i+2 acts as a
// pointer that points
// to the third value of
// every possible quadruplet
ans += arr[i + 2];
}
// Returning the optimally
// maximum possible value
return ans;
}
// Driver code
// Array declaration
var arr = [2, 1, 7, 5, 5, 4, 1, 1, 3, 3, 2, 2];
// Size of array
var n = arr.length;
document.write(formQuadruplets(arr, n) + "<br>");
</script>
Producción:
10
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(1)