Dadas dos arrays arr[] y brr[] de tamaño N y un entero K . Considere dos conjuntos A , que contiene K inicialmente, y B , inicialmente vacío. En cada operación, se requiere seleccionar un índice. Para cada índice seleccionado, digamos i , arr[i] y brr[i] se agregan a B . Para cada índice no seleccionado, arr[i] se agrega a A. La tarea es encontrar el número mínimo de índices necesarios para seleccionar para que la suma de B sea mayor que la suma de A.. Si no es posible hacerlo, imprima -1.
Ejemplos:
Entrada: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 12 Salida: 3 4 3 1 Explicación: Se seleccionan los índices 2
, 3
y
0 . Suma de B = arr[0] + brr[0] + arr[2] + brr[2] + arr[3] + brr[3] = 3 + 4 + 5 + 2 + 6 + 3 = 23. Suma de A = K + arr[1] = 12 + 2 = 14.Entrada: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 34
Salida: -1
Enfoque: La idea es utilizar un Enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de par, B[] para realizar un seguimiento de los índices.
- Inicialice una variable, A con K para almacenar el valor del conjunto A.
- Recorra la array arr[] usando la variable i ,
- Agregue el valor arr[i] a A , si no se eligió el índice.
- Inserta {brr[i] + 2 * arr[i], i} como un par en el vector B .
- Ordena el vector B en orden decreciente.
- Inicializar un vector, ans para almacenar los índices que se elijan.
- Ejecute un bucle while y siga eligiendo los índices hasta que el valor de A sea mayor que el de B.
- Si se eligen todos los índices pero el valor de B sigue siendo menor que A , imprima «-1» .
- De lo contrario, imprima el tamaño del vector y como el número mínimo de movimientos.
- Recorra el vector , ans , e imprima los índices elegidos.
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 print the minimum number
// of indices required to be selected
void numberOfIndexes(int arr[], int brr[],
int N, int K)
{
// Declare vector to keep track of indexes
vector<pair<int, int> > B;
// Set A contains K
int A = K;
// Traverse the array
for (int i = 0; i < N; i++) {
// Adding value that set A can
// get if no index was chosen
A += arr[i];
// Insert as B's value
B.push_back({ brr[i] + 2 * arr[i], i });
}
// Sort the vector
sort(B.begin(), B.end());
// Reverse the vector
reverse(B.begin(), B.end());
int tot = 0, idx = 0;
// Stores chosen indexes
vector<int> ans;
// Keep on choosing more indices until
// B's value is bigger than A or stop
// incase all the indexes is chosen
while (A >= tot && idx < B.size()) {
// Update tot
tot += B[idx].first;
// Update ans
ans.push_back(B[idx].second);
// Increment idx
idx++;
}
// If all indices are selected and
// sum of B is less than sum of A
if (tot <= A) {
cout << -1 << endl;
return;
}
// Print the minimum number of indices
cout << ans.size() << endl;
// Print chosen indices
for (auto c : ans)
cout << c + 1 << " ";
}
// Driver Code
int main()
{
// Given arrays
int arr[] = { 3, 2, 5, 6 };
int brr[] = { 4, 4, 2, 3 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given value of K
int K = 12;
// Function Call
numberOfIndexes(arr, brr, N, K);
return 0;
}
Python3
# Python 3 program for the above approach # Function to print the minimum number # of indices required to be selected def numberOfIndexes(arr, brr, N, K): # Declare vector to keep track of indexes B = [] # Set A contains K A = K # Traverse the array for i in range(N): # Adding value that set A can # get if no index was chosen A += arr[i] # Insert as B's value B.append([brr[i] + 2 * arr[i], i]) # Sort the vector B.sort() # Reverse the vector B = B[::-1] tot = 0 idx = 0 # Stores chosen indexes ans = [] # Keep on choosing more indices until # B's value is bigger than A or stop # incase all the indexes is chosen while (A >= tot and idx < len(B)): # Update tot tot += B[idx][0] # Update ans ans.append(B[idx][1]) # Increment idx idx += 1 # If all indices are selected and # sum of B is less than sum of A if (tot <= A): print(-1) return # Print the minimum number of indices print(len(ans)) # Print chosen indices for c in ans: print(c + 1,end = " ") # Driver Code if __name__ == '__main__': # Given arrays arr = [3, 2, 5, 6] brr = [4, 4, 2, 3] # Size of the array N = len(arr) # Given value of K K = 12 # Function Call numberOfIndexes(arr, brr, N, K) # This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to print the minimum number
// of indices required to be selected
function numberOfIndexes(arr, brr, N, K) {
// Declare vector to keep track of indexes
let B = [];
// Set A contains K
let A = K;
// Traverse the array
for (let i = 0; i < N; i++) {
// Adding value that set A can
// get if no index was chosen
A += arr[i];
// Insert as B's value
B.push([brr[i] + 2 * arr[i], i]);
}
// Sort the vector
// Reverse the vector
B.sort((a, b) => a[0] - b[0]).reverse();
let tot = 0,
idx = 0;
// Stores chosen indexes
let ans = [];
// Keep on choosing more indices until
// B's value is bigger than A or stop
// incase all the indexes is chosen
while (A >= tot && idx < B.length) {
// Update tot
tot += B[idx][0];
// Update ans
ans.push(B[idx][1]);
// Increment idx
idx++;
}
// If all indices are selected and
// sum of B is less than sum of A
if (tot <= A) {
document.write(-1 + "<br>");
return;
}
// Print the minimum number of indices
document.write(ans.length + "<br>");
// Print chosen indices
for (let c of ans) document.write(Number(c) + 1 + " ");
}
// Driver Code
// Given arrays
let arr = [3, 2, 5, 6];
let brr = [4, 4, 2, 3];
// Size of the array
let N = arr.length;
// Given value of K
let K = 12;
// Function Call
numberOfIndexes(arr, brr, N, K);
</script>
3 4 3 1
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ashutoshrathi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA