Saltar al contenido

Dividir el elemento máximo en N grupos para que recibido y requerido tengan una diferencia máxima de K

Dadas dos matrices A[] y B[] de tamaño norte y metro indicar los elementos requeridos de cada grupo y el número de elementos en un paquete, respectivamente. La tarea es distribuir el máximo número de paquetes para que la diferencia en el número de elementos que recibe un grupo y su necesidad sea máxima. k.

Ejemplos:

Aporte: norte = 4, metro = 3, k = 5, un[] = [60, 45, 80, 60]B[] = [30, 60, 75]
Salida: 2
Explicación: Los 2 paquetes que se distribuirán son los siguientes.
El paquete de tamaño 60 se distribuye al grupo con
requisito 60 como 60 – 5 < 60 en 60 + 5 > 60 .
El paquete cuyo tamaño es 75 se distribuirá entre el grupo con
requisito 80 si 80 – 5 = 75 y 80 + 5 > 75.

Aporte: norte = 4, metro = 3, k = 10, un[] = [60, 40, 80, 60]B[] = [30, 60, 75]
Salida: 3
Explicación: Todos los paquetes serán distribuidos en esta situación.
El paquete cuyo tamaño es 30 se distribuirá entre el grupo con
requisito 40 si 40 – 10 = 30 y 40 + 10 > 30.
El paquete de tamaño 60 se distribuye al grupo con
requisito 60 como 60 – 10 < 60 en 60 + 10 > 60
El paquete cuyo tamaño es 75 se distribuirá entre el grupo con
requisito 80 como 80 – 10 < 75 en 80 + 10 > 75.

Acercarse: El problema se puede resolver usando para ordenar en base a la siguiente idea:

Ordenar ambas matrices. Ahora busque con avidez el primer grupo con un requisito que se ha cumplido y, entre todos los paquetes posibles, asigne el paquete con un número mínimo de elementos, para que las opciones estén disponibles para grupos con requisitos más altos.

Siga los pasos a continuación para implementar la idea:

  • Ordenar matriz A[] y B[].
  • Después de ordenar ambas matrices, use dos punteros i y y para repetir A y B respectivamente.
  • Inicializar una variable (digamos centavo = 0) para guardar la respuesta.
  • Ahora comience a iterar a través de las matrices:
    • Si desea el tamaño del paquete para el grupo, aumente no, i y y.
    • Si el requerimiento del grupo después de deducir la diferencia máxima k es más grande que el tamaño del paquete, entonces este paquete no puede ser utilizado por ningún grupo. Por lo tanto aumentar y.
    • Si el paquete excede la necesidad del grupo después de agregar: k, entonces no hay ningún paquete para ese grupo. Por lo tanto aumentar i.
  • Dar el … Volver centavo variable como la respuesta requerida.

A continuación encontrará la implementación del enfoque anterior.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int desired_size(int N, int M, int K,

                 vector<int>& A, vector<int>& B)

{

    

    sort(A.begin(), A.end());

 

    

    sort(B.begin(), B.end());

 

    

    

    int i = 0, j = 0;

 

    

    int cnt = 0;

 

    

    while (i < N && j < M) {

 

        

        

        

        if (A[i] - K <= B[j] && A[i] + K >= B[j]) {

            cnt++;

            i++;

            j++;

        }

 

        

        

        

        else if (A[i] - K > B[j]) {

            j++;

        }

 

        

        

        

        else if (A[i] + K < B[j]) {

            i++;

        }

    }

 

    

    return cnt;

}

 

int main()

{

    int N = 4;

    int M = 3;

    int K = 5;

 

    vector<int> A = { 60, 45, 80, 60 };

    vector<int> B = { 30, 60, 75 };

 

    

    cout << desired_size(N, M, K, A, B);

    return 0;

}

Complejidad del tiempo: O(D * logD) donde D es el máximo entre N y M
cuarto auxiliar: O(1)