Recuento máximo de pares tal que el elemento en cada índice i se incluye en i pares

Dada una array arr[] y un número entero N , la tarea es encontrar el número máximo de pares que se pueden formar de modo que el i ^-ésimo índice esté incluido en casi arr[i] pares.

Ejemplos:

Entrada : arr[] = {2, 2, 3, 4} 
Salida : 
5
1 3
2 4
2 4
3 4
3 4
Explicación : para la array dada, se pueden crear un máximo de 5 pares donde el primer índice se incluye en 1 par, 2do índice en 2 pares, 3er índice en 3 pares y 4to índice en 4 pares como se muestra arriba. 

Entrada : arr[] = {8, 2, 0, 1, 1}
Salida : 
4
1 2
1 5
1 4
1 2

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . Se puede observar que la elección más óptima en cada paso es elegir los elementos con el valor máximo y crear su respectivo par. Usando esta observación, siga los pasos a continuación para resolver este problema: 

• Cree una cola de prioridad máxima que almacene los índices de la array dada en orden decreciente de su valor de array respectivo.
• Cree un ciclo para iterar la cola de prioridad hasta que haya más de dos elementos y siga los pasos a continuación:
  • Seleccione los dos índices principales en la cola de prioridad, agregue su par en una array de respuesta .
  • Vuelva a insertarlos en la cola de prioridad después de disminuir sus respectivos valores de array si sus valores son mayores que 0.
• Imprime todos los pares en la array de respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
void maxPairs(int arr[], int n)
{
    // Stores the final list
    // of pairs required
    vector<int> matchList;
     
    // Max Priority Queue to
    // store induced in order
    // of their array value
    priority_queue<int> pq;
     
    // Loop to iterate arr[]
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
            pq.push(i);
    }
  
    // Loop to iterate pq
    // till it has more
    // than 2 elements
    while (pq.size() >= 2)
    {
        // Stores the maximum
        int top = pq.top();
        pq.pop();
  
        // Stores the second
        // maximum
        int cur = pq.top();
        pq.pop();
  
        // Insert pair into the
        // final list
        matchList.push_back(top + 1);
        matchList.push_back(cur + 1);
        arr[top]--;
        arr[cur]--;
  
        if (arr[top] > 0)
            pq.push(top);
  
        if (arr[cur] > 0)
            pq.push(cur);
    }
     
    // Print Answer
    cout << (matchList.size() / 2) << "\n";
    for (int i = 0; i < matchList.size(); i += 2)
    {
        cout << matchList[i] << " " << matchList[i+1] << "\n";
    }
}
  
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    maxPairs(arr,n);
  
    return 0;
}
 
// This code is contributed by Aditya Patil

// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG {
    public static void maxPairs(int arr[])
    {
        // Stores the final list
        // of pairs required
        List<Integer> matchList = new ArrayList<>();
  
        // Max Priority Queue to
        // store induced in order
        // of their array value
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (x, y) -> arr[y] - arr[x]);
  
        // Loop to iterate arr[]
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0)
                pq.add(i);
        }
  
        // Loop to iterate pq
        // till it has more
        // than 2 elements
        while (pq.size() >= 2) {
  
            // Stores the maximum
            int top = pq.poll();
  
            // Stores the second
            // maximum
            int cur = pq.poll();
  
            // Insert pair into the
            // final list
            matchList.add(top + 1);
            matchList.add(cur + 1);
            arr[top]--;
            arr[cur]--;
  
            if (arr[top] > 0)
                pq.add(top);
  
            if (arr[cur] > 0)
                pq.add(cur);
        }
  
        // Print Answer
        System.out.println(matchList.size() / 2);
        for (int i = 0; i < matchList.size(); i += 2) {
            System.out.println(matchList.get(i) + " "
                               + matchList.get(i + 1));
        }
    }
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4 };
        maxPairs(arr);
    }
}

5
4 3
4 3
2 4
3 4
2 1

Complejidad de tiempo: O(M*log M), donde M denota la suma de todos los elementos de la array
Espacio auxiliar: O(N)