Dadas dos arrays A[] y B[] de N enteros, la tarea es encontrar para cada elemento A[i], el tamaño del subconjunto más pequeño S de índices, tal que:
- Cada valor correspondiente a los índices en el subconjunto S es estrictamente menor que A[i] .
- La suma de los elementos correspondientes a los índices en B es estrictamente mayor que B[i] .
Ejemplos:
Entrada: N = 5, A = {3, 2, 100, 4, 5}, B = {1, 2, 3, 4, 5} Salida: {1, -1, 1, -1, 3
} Explicación
: Los subconjuntos para cada elemento de A son:
A[0]: {1}, (A[1] < A[0] y B[1] > B[0])
A[1]: {}, (no existe tal subconjunto existe)
A[2]: {4}, (A[4] < A[2] y B[4] > B[2])
A[3]: {}, (no existe tal subconjunto)
A[4] : {0, 1, 3}, (A[0] < A[4], A[1] < A[4], A[3] < A[4] y (B[0]+B[1] +B[3] > B[4]) )Entrada: N = 4, A = {1, 1, 1, 1}, B = {2, 4, 5, 9}
Salida: {-1, -1, -1, -1}
Enfoque: el problema se puede resolver mediante un enfoque codicioso utilizando un conjunto múltiple según la siguiente idea:
Ordene la array A[] junto con sus índices y, para cada elemento de la array ordenada, encuentre el subconjunto más pequeño que tenga elementos de B con una suma mayor que el elemento actual de B. Use multiset
en orden decreciente para almacenar elementos de B.
Siga los pasos a continuación para resolver este problema:
- Declare un vector v de pares, que almacene los elementos de la array A junto con sus índices.
- Ordenar el vector v . Después de la clasificación, se cumple la primera condición para cada elemento.
- Declare un multiset s para que los elementos en multiset estén en orden decreciente.
- Iterar a través del vector v y en cada i-ésima iteración:
- Almacene el elemento en la array B correspondiente al índice en el i-ésimo elemento del vector (es decir, el segundo elemento del par) en una variable, digamos curr_B.
- Iterar a través del conjunto, manteniendo simultáneamente el conteo y la suma de los elementos del conjunto, hasta que la suma sea apenas mayor que curr_B .
- Inserte curr_B en el conjunto y cuente (del conjunto requerido) encontrado para el i-ésimo elemento en la array que almacena la respuesta ( respuesta).
- Devuelve el vector ans después de completar todas las iteraciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Find minimum size of subset
// for each index of the array satisfying the
// given condition
#include <bits/stdc++.h>
using namespace std;
// Functions to print minimum size of subset
// for each element satisfying the given conditions
void printSubsets(int N, int A[], int B[])
{
// storing the elements of A along with
// their indices in a vector of pairs v
vector<pair<int, int> > v(N);
for (int i = 0; i < N; i++) {
v[i] = { A[i], i };
}
// sorting the vector v
sort(v.begin(), v.end());
// declaring a vector of size N to
// store the answer
vector<int> ans(N);
// declaring a multiset to store the
// corresponding values of B
multiset<int, greater<int> > s;
// iterating through the sorted vector v.
// Since the vector is sorted, so the 1st
// condition is already fulfilled, i.e.
// all the elements of A at indices of resultant
// set would be less than current A[i]
for (int i = 0; i < N; i++) {
int curr_B = B[v[i].second];
int size = 0;
int sum = 0;
// iterating through the set to find
// the minimum set whose sum>B[i]
//(or curr_B)
for (auto x : s) {
sum += x;
size += 1;
if (sum > curr_B)
break;
}
// inserting the current element of B
// into the set
s.insert(curr_B);
// if sum>B[i] condition is fulfilled,
// we assign size of resultant subset to
// the answer at the index
if (sum > curr_B) {
ans[v[i].second] = size;
}
// else we assign -1
else {
ans[v[i].second] = -1;
}
}
// printing the answer
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
int N = 5;
int A[] = { 3, 2, 100, 4, 5 };
int B[] = { 1, 2, 4, 3, 5 };
printSubsets(N, A, B);
}
Java
import java.util.*;
import java.io.*;
// Java program for Find minimum size of subset
// for each index of the array satisfying the
// given condition
class GFG{
// Functions to print minimum size of subset
// for each element satisfying the given conditions
public static void printSubsets(int N, int A[], int B[]){
// Storing the elements of A along with
// their indices in a arrayList of pairs v
Pair v[] = new Pair[N];
for(int i = 0 ; i < N ; i++){
v[i] = new Pair(A[i], i);
}
// Sorting the array v
Arrays.sort(v, new comp());
// Declaring a array of size N to
// store the answer
int ans[] = new int[N];
// Declaring a map to store the corresponding
// values of B
TreeMap<Integer, Integer> s = new TreeMap<Integer,Integer>();
// iterating through the sorted arraylist v.
// Since the arraylist is sorted, so the 1st
// condition is already fulfilled, i.e.
// all the elements of A at indices of resultant
// set would be less than current A[i]
for (int i = 0 ; i < N ; i++) {
int curr_B = B[v[i].second];
int size = 0;
int sum = 0;
// iterating through the set to find
// the minimum set whose sum>B[i]
//(or curr_B)
for (Map.Entry<Integer, Integer> x : s.entrySet()) {
for(int j=1 ; j<=x.getValue() ; j++){
sum += (-x.getKey());
size += 1;
if (sum > curr_B)
break;
}
if (sum > curr_B)
break;
}
// inserting the current element of B
// into the TreeMap
if(s.containsKey(-curr_B)){
s.put(-curr_B, s.get(-curr_B)+1);
}else{
s.put(-curr_B, 1);
}
// if sum>B[i] condition is fulfilled,
// we assign size of resultant subset to
// the answer at the index
if (sum > curr_B) {
ans[v[i].second] = size;
}
// else we assign -1
else {
ans[v[i].second] = -1;
}
}
// printing the answer
for (int i = 0; i < N; i++) {
System.out.print(ans[i] + " ");
}
}
// Driver code
public static void main(String args[])
{
int N = 5;
int A[] = {3, 2, 100, 4, 5};
int B[] = {1, 2, 4, 3, 5};
printSubsets(N, A, B);
}
}
class Pair{
Integer first;
Integer second;
Pair(int x, int y){
this.first = x;
this.second = y;
}
}
class comp implements Comparator<Pair>{
public int compare(Pair x, Pair y){
if(x.first.equals(y.first)){
return x.second.compareTo(y.second);
}
return x.first.compareTo(y.first);
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python program to find the minimum size of the subset
# for each index of the array satisfying the given condition
import bisect
#Functions to print minimum size of subset
#for each element satisfying the given conditions
def printSubsets(N, A, B):
#storing the elements of A along with
#their indices in a vector of pairs v
v = [[A[i], i] for i in range(N)]
v.sort() #sorting v
#initializing ans, s
ans = [0] * N
s = list()
for i in range(N):
curr_B = B[v[i][1]]
size = 0
sums = 0
for ele in s:
sums += ele
size += 1
if sums > curr_B:
break
#to ensure that sorted status of s is maintained
bisect.insort(s, curr_B)
if (sums > curr_B):
ans[v[i][1]] = size
else:
ans[v[i][1]] = -1
print(" ".join(list(map(str, ans))))
# Driver Code
N = 5
A = [3, 2, 100, 4, 5]
B = [1, 2, 4, 3, 5]
printSubsets(N, A, B)
# This code is contributed by phalasi.
Javascript
<script>
// JS program for Find minimum size of subset
// for each index of the array satisfying the
// given condition
// Functions to print minimum size of subset
// for each element satisfying the given conditions
function printSubsets(N, A, B)
{
// storing the elements of A along with
// their indices in a vector of pairs v
var v = [];
for (var i = 0; i < N; i++) {
v.push([ A[i], i ]);
}
// sorting the vector v
v.sort();
// declaring a vector of size N to
// store the answer
var ans = new Array(N).fill(0);
// declaring a multiset to store the
// corresponding values of B
var s = [];
// iterating through the sorted vector v.
// Since the vector is sorted, so the 1st
// condition is already fulfilled, i.e.
// all the elements of A at indices of resultant
// set would be less than current A[i]
for (var i = 0; i < N; i++) {
var curr_B = B[v[i][1]];
var size = 0;
var sum = 0;
// iterating through the set to find
// the minimum set whose sum>B[i]
//(or curr_B)
for (var j = 0; j < s.length; j++) {
sum += s[j];
size += 1;
if (sum > curr_B)
break;
}
// inserting the current element of B
// into the sorted list s
// this implementation mimics
// C++ multiset or Python insort.
var ind = 0;
for (var j = 0; j < s.length; j++) {
if (s[j] > curr_B)
break;
ind++;
}
s.splice(ind, 0, curr_B);
// if sum>B[i] condition is fulfilled,
// we assign size of resultant subset to
// the answer at the index
if (sum > curr_B) {
ans[v[i][1]] = size;
}
// else we assign -1
else {
ans[v[i][1]] = -1;
}
}
// printing the answer
for (var i = 0; i < N; i++) {
document.write(ans[i] + " ");
}
}
// Driver Code
var N = 5;
var A = [ 3, 2, 100, 4, 5 ];
var B = [ 1, 2, 4, 3, 5 ];
printSubsets(N, A, B);
// This code is contributed by phasing17.
</script>
Producción
1 -1 1 -1 3
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA