Conteo de reducciones mínimas requeridas para obtener la suma requerida K

Dados N pares de enteros y un entero K , la tarea es encontrar el número mínimo de reducciones necesarias para que la suma de los primeros elementos de cada par sea ≤ K . Cada reducción consiste en reducir el primer valor de un par a su segundo valor . Si no es posible hacer la suma ≤ K , imprima -1.

Ejemplos:  
Entrada: N = 5, K = 32 
10 6 
6 4 
8 5 
9 8 
5 2 
Salida: 2 
Explicación: 
Suma total = 10 + 6 + 8 + 9 + 5 = 38 > K 
Reducción de 10 – > 6 y 8 – > 5 reduce la suma a 31( 6 + 6 + 5 + 9 + 5) que es menor que K.

Entrada: N = 4, K = 25 
10 5 
20 9 
12 10 
4 2 
Salida: -1 

Enfoque: 
siga los pasos a continuación para resolver el problema: 

1. Calcula la suma del primer elemento de cada par. Si la suma ya es ≤ K, imprima 0.
2. Ordena los pares dados según su diferencia.
3. Cuente el número de diferencias de pares que deben agregarse en orden no creciente para que la suma sea menor que K .
4. Si la suma excede K después del recorrido de todos los pares, imprima -1. De lo contrario, imprima el conteo.

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

// C++ Program to find the count of
// minimum reductions required to
// get the required sum K
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of minimum reductions
int countReductions(
    vector<pair<int, int> >& v,
    int K)
{
 
    int sum = 0;
    for (auto i : v) {
        sum += i.first;
    }
 
    // If the sum is already
    // less than K
    if (sum <= K) {
        return 0;
    }
 
    // Sort in non-increasing
    // order of difference
    sort(v.begin(), v.end(),
         [&](
             pair<int, int> a,
             pair<int, int> b) {
             return (a.first - a.second)
                    > (b.first - b.second);
         });
 
    int i = 0;
    while (sum > K && i < v.size()) {
        sum -= (v[i].first
                - v[i].second);
        i++;
    }
 
    if (sum <= K)
        return i;
 
    return -1;
}
 
// Driver Code
int main()
{
    int N = 4, K = 25;
 
    vector<pair<int, int> > v(N);
    v[0] = { 10, 5 };
    v[1] = { 20, 9 };
    v[2] = { 12, 10 };
    v[3] = { 4, 2 };
 
    // Function Call
    cout << countReductions(v, K)
         << endl;
    return 0;
}

// Java program to find the count of
// minimum reductions required to
// get the required sum K
import java.util.*;
 
class GFG{
     
// Function to return the count
// of minimum reductions
static int countReductions(ArrayList<int[]> v,
                           int K)
{
    int sum = 0;
    for(int[] i : v)
    {
        sum += i[0];
    }
 
    // If the sum is already
    // less than K
    if (sum <= K)
    {
        return 0;
    }
 
    // Sort in non-increasing
    // order of difference
    Collections.sort(v, (a, b) -> Math.abs(b[0] - b[1]) -
                                  Math.abs(a[0] - a[1]));
 
    int i = 0;
    while (sum > K && i < v.size())
    {
        sum -= (v.get(i)[0] - v.get(i)[1]);
        i++;
    }
 
    if (sum <= K)
        return i;
 
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4, K = 25;
 
    ArrayList<int[]> v = new ArrayList<>();
 
    v.add(new int[] { 10, 5 });
    v.add(new int[] { 20, 9 });
    v.add(new int[] { 12, 10 });
    v.add(new int[] { 4, 2 });
 
    // Function Call
    System.out.println(countReductions(v, K));
}
}
 
// This code is contributed by offbeat

# Python3 program to find the count of
# minimum reductions required to
# get the required sum K
from typing import Any, List
 
# Function to return the count
# of minimum reductions
def countReductions(v: List[Any], K: int) -> int:
 
    sum = 0
     
    for i in v:
        sum += i[0]
 
    # If the sum is already
    # less than K
    if (sum <= K):
        return 0
 
    # Sort in non-increasing
    # order of difference
    v.sort(key = lambda a : a[0] - a[1])
 
    i = 0
     
    while (sum > K and i < len(v)):
        sum -= (v[i][0] - v[i][1])
        i += 1
 
    if (sum <= K):
        return i
 
    return -1
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    K = 25
 
    v = [[0, 0] for _ in range(N)]
    v[0] = [10, 5]
    v[1] = [20, 9]
    v[2] = [12, 10]
    v[3] = [4, 2]
 
    # Function Call
    print(countReductions(v, K))
 
# This code is contributed by sanjeev2552

-1

Complejidad temporal: O(NlogN)  
Espacio auxiliar: O(1)