Dadas dos arrays A[] y B[] que constan de N enteros y un entero K , la tarea es maximizar la suma calculada a partir de la array A[] mediante las siguientes operaciones:
- Para cada índice en B[] que contiene 0 , el índice correspondiente en A[] se suma a la suma .
- Para cada índice en B[] que contenga 1 , agregue el valor en el índice correspondiente en A[] a la suma de como máximo K índices. Para los índices restantes, reste de la suma.
Ejemplos:
Entrada: A[] = {5, 4, 6, 2, 8}, B[] = {1, 0, 1, 1, 0}, K = 2
Salida: 21
Explicación:
Sume A[1] y A[ 4] a la suma como B[1] = B[4] = 0
Por lo tanto, sum = 4 + 8 = 12.
Ahora, agregue A[0] y A[3] a la suma como se pueden agregar K elementos.
Finalmente, resta 2 de la suma.
Por lo tanto, la suma máxima posible = 12 + 5 + 6 – 2 = 21
Entrada: A[] = {5, 2, 1, 8, 10, 5}, B[] = {1, 1, 1, 1, 0 , 0}, K = 3
Salida: 29
Acercarse:
Siga los pasos a continuación para resolver el problema:
- Ordene la array A[] en orden decreciente.
- Para maximizar la suma, agregue los primeros K elementos de la array ordenada correspondiente a la que el índice en B[] contiene 1 . Reste los elementos restantes de este tipo.
- Agregue a la suma todos los valores en A[] correspondientes a un índice en B[] que contenga 0 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to maximize the
// sum of the given array
#include <bits/stdc++.h>
using namespace std;
// Comparator to sort the array
// in ascending order
bool compare(pairs<int, int> p1,
pairs<int, int> p2)
{
return p1.first > p2.first;
}
// Function to maximize the sum of
// the given array
int maximizeScore(int A[], int B[],
int K, int N)
{
// Stores {A[i], B[i]} pairs
vector<pairs<int, int> > pairs(N);
for (int i = 0; i < N; i++) {
pairs[i] = make_pairs(A[i], B[i]);
}
// Sort in descending order of the
// values in the array A[]
sort(pairs.begin(), pairs.end(), compare);
// Stores the maximum sum
int sum = 0;
for (int i = 0; i < N; i++) {
// If B[i] is equal to 0
if (pairs[i].second == 0) {
// Simply add A[i] to the sum
sum += pairs[i].first;
}
else if (pairs[i].second == 1) {
// Add the highest K numbers
if (K > 0) {
sum += pairs[i].first;
K--;
}
// Subtract from the sum
else {
sum -= pairs[i].first;
}
}
}
// Return the sum
return sum;
}
// Driver Code
int main()
{
int A[] = { 5, 4, 6, 2, 8 };
int B[] = { 1, 0, 1, 1, 0 };
int K = 2;
int N = sizeof(A) / sizeof(int);
cout << maximizeScore(A, B, K, N);
return 0;
}
Java
// Java program to maximise the
// sum of the given array
import java.util.*;
class Pairs implements Comparable<Pairs>
{
int first, second;
Pairs(int x, int y)
{
first = x;
second = y;
}
public int compareTo(Pairs p)
{
return p.first - first;
}
}
class GFG{
// Function to maximise the sum of
// the given array
static int maximiseScore(int A[], int B[],
int K, int N)
{
// Stores {A[i], B[i]} pairs
ArrayList<Pairs> pairs = new ArrayList<>();
for(int i = 0; i < N; i++)
{
pairs.add(new Pairs(A[i], B[i]));
}
// Sort in descending order of the
// values in the array A[]
Collections.sort(pairs);
// Stores the maximum sum
int sum = 0;
for(int i = 0; i < N; i++)
{
// If B[i] is equal to 0
if (pairs.get(i).second == 0)
{
// Simply add A[i] to the sum
sum += pairs.get(i).first;
}
else if (pairs.get(i).second == 1)
{
// Add the highest K numbers
if (K > 0)
{
sum += pairs.get(i).first;
K--;
}
// Subtract from the sum
else
{
sum -= pairs.get(i).first;
}
}
}
// Return the sum
return sum;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 5, 4, 6, 2, 8 };
int B[] = { 1, 0, 1, 1, 0 };
int K = 2;
int N = A.length;
System.out.print(maximiseScore(A, B, K, N));
}
}
// This code is contributed by jrishabh99
Python3
# Python Program to maximise the
# sum of the given array
# Comparator to sort the array
# in ascending order
def compare(p1, p2):
return p1[0] > p2[0]
# Function to maximise the sum of
# the given array
def maximiseScore(A, B, K, N):
# Stores {A[i], B[i]} pairs
pairs = []
for i in range(N):
pairs.append([A[i], B[i]])
# Sort in descending order of the
# values in the array A[]
pairs.sort(key = lambda x:x[0], reverse = True)
# Stores the maximum sum
Sum = 0
for i in range(N):
# If B[i] is equal to 0
if(pairs[i][1] == 0):
# Simply add A[i] to the sum
Sum += pairs[i][0]
elif(pairs[i][1] == 1):
# Add the highest K numbers
if(K > 0):
Sum += pairs[i][0]
K -= 1
# Subtract from the sum
else:
Sum -= pairs[i][0]
# Return the sum
return Sum
# Driver Code
A = [5, 4, 6, 2, 8]
B = [1, 0, 1, 1, 0]
K = 2
N = len(A)
print(maximiseScore(A, B, K, N))
# This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript Program to maximize the
// sum of the given array
// Comparator to sort the array
// in ascending order
function compare(p1,p2)
{
return p2[0] - p1[0];
}
// Function to maximize the sum of
// the given array
function maximizeScore(A, B, K, N)
{
// Stores {A[i], B[i]} pairs
let pairs = new Array(N);
for (let i = 0; i < N; i++) {
pairs[i] = [A[i], B[i]];
}
// Sort in descending order of the
// values in the array A[]
pairs.sort(compare);
// Stores the maximum sum
let sum = 0;
for (let i = 0; i < N; i++) {
// If B[i] is equal to 0
if (pairs[i][1] == 0) {
// Simply add A[i] to the sum
sum += pairs[i][0];
}
else if (pairs[i][1] == 1) {
// Add the highest K numbers
if (K > 0) {
sum += pairs[i][0];
K--;
}
// Subtract from the sum
else {
sum -= pairs[i][0];
}
}
}
// Return the sum
return sum;
}
// Driver Code
let A = [ 5, 4, 6, 2, 8 ];
let B = [ 1, 0, 1, 1, 0 ];
let K = 2;
let N = A.length;
document.write(maximizeScore(A, B, K, N),"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción:
21
Complejidad temporal: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA