Dadas dos arrays , arr[] de tamaño N y div[] de tamaño K. Divida arr[] en K arrays diferentes, cada una de tamaño div[i] . La tarea es encontrar la suma total después de maximizar la suma del máximo y el mínimo de cada array dividida.
Ejemplos:
Entrada: arr[] = {3, 1, 7, 4}, div[] = {1, 3}, N = 4, K = 2
Salida: 19
Explicación: Divida la array de la siguiente manera:
- {7}, suma de máximo y mínimo = (7 + 7) = 14
- {1, 3, 4}, suma de máximo y mínimo = (4 + 1) = 5
Suma total = 14 + 5 = 19.
Entrada: arr[] = {10, 12, 10, 12, 10, 12}, div[] = {3, 3}, N = 6, K = 2
Salida: 44
Enfoque: siga los pasos a continuación para resolver el problema:
- Tome una variable digamos count1 para contar un número de 1 en div[] .
- Ordene ambas arrays, arr[] en orden descendente y div[] en orden ascendente .
- Tome una variable, digamos, ans para almacenar la respuesta y otra variable, digamos t, que representa desde qué índice se iniciará la iteración en div[] .
- Itere la array hasta K , en cada iteración agregue los elementos a ans, y agregue ese elemento nuevamente a ans mientras count1 es mayor que 0 porque las arrays de tamaño 1 tienen el mismo elemento como máximo y mínimo .
- Nuevamente, itere un bucle desde el índice Kth hasta el final de la array. Agregue un elemento a ans y actualice el índice.
- Devuelve la 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 find the total sum after
// maximizing the sum of maximum and
// minimum of each divided array
int maximizeSum(int arr[], int divi[], int N, int K)
{
// Variable to count 1s in divi[]
int count1 = 0;
for (int i = 0; i < K; i++) {
if (divi[i] == 1) {
count1++;
}
}
// Sort arr[] in descending order
sort(arr, arr + N, greater<int>());
// Sort divi[] in ascending order
sort(divi, divi + K);
// Temporary variable to store
// the count of 1s in the divi[]
int t = count1;
// Variable to store answer
int ans = 0;
// Iterate over the array till K
for (int i = 0; i < K; i++) {
// Add the current element to ans
ans += arr[i];
// If count1 is greater than 0,
// decrement it by 1 and update the
// ans by again adding the same element
if (count1 > 0) {
count1--;
ans += arr[i];
}
}
// Traverse the array from Kth index
// to the end
for (int i = K; i < N; i++) {
// Update the index
i += divi[t] - 2;
// Add the value at that index to ans
ans += arr[i];
t++;
}
// Return ans
return ans;
}
// Driver Code
int main()
{
int arr[] = { 3, 1, 7, 4 };
int divi[] = { 1, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = sizeof(divi) / sizeof(divi[0]);
cout << maximizeSum(arr, divi, N, K);
return 0;
}
Java
// Java code for the above approach
import java.util.Arrays;
import java.util.Collections;
class GFG
{
// Function to find the total sum after
// maximizing the sum of maximum and
// minimum of each divided array
static int maximizeSum(int arr[], int divi[], int N,
int K)
{
// Variable to count 1s in divi[]
int count1 = 0;
for (int i = 0; i < K; i++) {
if (divi[i] == 1) {
count1++;
}
}
// Sort arr[] in descending order
Arrays.sort(arr);
reverse(arr);
// Sort divi[] in ascending order
Arrays.sort(divi);
// Temporary variable to store
// the count of 1s in the divi[]
int t = count1;
// Variable to store answer
int ans = 0;
// Iterate over the array till K
for (int i = 0; i < K; i++) {
// Add the current element to ans
ans += arr[i];
// If count1 is greater than 0,
// decrement it by 1 and update the
// ans by again adding the same element
if (count1 > 0) {
count1--;
ans += arr[i];
}
}
// Traverse the array from Kth index
// to the end
for (int i = K; i < N; i++) {
// Update the index
i += divi[t] - 2;
// Add the value at that index to ans
ans += arr[i];
t++;
}
// Return ans
return ans;
}
public static void reverse(int[] array)
{
// Length of the array
int n = array.length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++) {
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 1, 7, 4 };
int divi[] = { 1, 3 };
int N = arr.length;
int K = divi.length;
System.out.println(maximizeSum(arr, divi, N, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python program for the above approach # Function to find the total sum after # maximizing the sum of maximum and # minimum of each divided array def maximizeSum(arr, divi, N, K): # Variable to count 1s in divi[] count1 = 0 for i in range(K): if (divi[i] == 1): count1 += 1 # Sort arr[] in descending order arr.sort() arr.reverse() # Sort divi[] in ascending order divi.sort() # Temporary variable to store # the count of 1s in the divi[] t = count1 # Variable to store answer ans = 0 # Iterate over the array till K for i in range(K): # Add the current element to ans ans += arr[i] # If count1 is greater than 0, # decrement it by 1 and update the # ans by again adding the same element if (count1 > 0): count1 -= 1 ans += arr[i] # Traverse the array from Kth index # to the end i = K while(i < N): # Update the index i += divi[t] - 2 # Add the value at that index to ans ans += arr[i] t += 1 i += 1 # Return ans return ans # Driver Code arr = [3, 1, 7, 4] divi = [1, 3] N = len(arr) K = len(divi) print(maximizeSum(arr, divi, N, K)) # This code is contributed by gfgking
C#
// C# code for the above approach
using System;
public class GFG
{
// Function to find the total sum after
// maximizing the sum of maximum and
// minimum of each divided array
static int maximizeSum(int []arr, int []divi, int N,
int K)
{
// Variable to count 1s in divi[]
int count1 = 0;
for (int i = 0; i < K; i++) {
if (divi[i] == 1) {
count1++;
}
}
// Sort arr[] in descending order
Array.Sort(arr);
reverse(arr);
// Sort divi[] in ascending order
Array.Sort(divi);
// Temporary variable to store
// the count of 1s in the divi[]
int t = count1;
// Variable to store answer
int ans = 0;
// Iterate over the array till K
for (int i = 0; i < K; i++) {
// Add the current element to ans
ans += arr[i];
// If count1 is greater than 0,
// decrement it by 1 and update the
// ans by again adding the same element
if (count1 > 0) {
count1--;
ans += arr[i];
}
}
// Traverse the array from Kth index
// to the end
for (int i = K; i < N; i++) {
// Update the index
i += divi[t] - 2;
// Add the value at that index to ans
ans += arr[i];
t++;
}
// Return ans
return ans;
}
public static void reverse(int[] array)
{
// Length of the array
int n = array.Length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++) {
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 3, 1, 7, 4 };
int []divi = { 1, 3 };
int N = arr.Length;
int K = divi.Length;
Console.WriteLine(maximizeSum(arr, divi, N, K));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to find the total sum after
// maximizing the sum of maximum and
// minimum of each divided array
const maximizeSum = (arr, divi, N, K) => {
// Variable to count 1s in divi[]
let count1 = 0;
for (let i = 0; i < K; i++) {
if (divi[i] == 1) {
count1++;
}
}
// Sort arr[] in descending order
arr.sort();
arr.reverse();
// Sort divi[] in ascending order
divi.sort();
// Temporary variable to store
// the count of 1s in the divi[]
let t = count1;
// Variable to store answer
let ans = 0;
// Iterate over the array till K
for (let i = 0; i < K; i++) {
// Add the current element to ans
ans += arr[i];
// If count1 is greater than 0,
// decrement it by 1 and update the
// ans by again adding the same element
if (count1 > 0) {
count1--;
ans += arr[i];
}
}
// Traverse the array from Kth index
// to the end
for (let i = K; i < N; i++) {
// Update the index
i += divi[t] - 2;
// Add the value at that index to ans
ans += arr[i];
t++;
}
// Return ans
return ans;
}
// Driver Code
let arr = [3, 1, 7, 4];
let divi = [1, 3];
let N = arr.length
let K = divi.length
document.write(maximizeSum(arr, divi, N, K));
// This code is contributed by rakeshsahni
</script>
Producción
19
Complejidad de tiempo: O(NlogN), tiempo requerido para clasificar
Espacio auxiliar: O(1)