Recuento de jugadores que necesitan entrenamiento y tienen estrictamente menos potencia y resistencia que cualquier otro jugador

Posted on by Rudeus Greyrat

Dados reproductores de array 2D con tres componentes [potencia, resistencia, id] . Un jugador necesita entrenamiento si tiene estrictamente menos potencia y resistencia que cualquier otro jugador. La tarea es encontrar el número de jugadores que necesitan entrenamiento con sus id s. 

Ejemplos:

Entrada: {{5, 4, 1}, {6, 3, 2}, {3, 5, 3}}
Salida: 0
Explicación: No hay jugador que tenga estrictamente mayor poder y resistencia que cualquier otro jugador.

Entrada: {{1, 1, 0}, {2, 2, 1}, {3, 3, 2}}
Salida: 2
             0 1
Explicación: A continuación se muestran los jugadores que necesitan entrenamiento
Jugador con id = 0, con poder = 1 y resistencia = 1 es estrictamente menor que el jugador con id = 2. 
El jugador con id = 1, que tiene potencia = 2 y resistencia = 2 es estrictamente menor que el jugador con id = 2.
Por lo tanto, hay 2 jugadores que necesitan entrenamiento. 

 

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . Sean X e Y los dos jugadores. El jugador X necesita entrenamiento si existe Y tal que la potencia de X < potencia de Y y la resistencia de X < resistencia de Y . Siga los pasos a continuación para resolver el problema dado. 

  • Se compararán dos jugadores sobre la base de dos parámetros.
  • Ordene la array players[][] en orden de potencia no decreciente.
  • Si dos elementos tienen el mismo valor de potencia, considere primero aquel cuyo valor de resistencia es mayor.
  • Iterar desde el lado derecho de la array players[][] y realizar un seguimiento de la resistencia máxima anterior.
    • Al principio, si algún jugador es elegible para entrenar, almacena su id .
    • Si la resistencia actual del jugador es menor que el valor máximo de resistencia anterior, aumente el número de jugadores.
    • De lo contrario, actualice el valor máximo de resistencia.
  • Devuelve la array que almacena todos los id de los jugadores que necesitan entrenamiento.

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

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
bool compare(vector<int>, vector<int>);
 
vector<int> CountOfPlayers(vector<vector<int> >& qualities)
{
    int count = 0;
    int n = qualities.size();
 
    sort(qualities.begin(), qualities.end(),
         [](vector<int>& entry1, vector<int>& entry2)
    {
       
             // If power value is equal
             // for both elements
             // Sort in descending order
             // according to endurance value
             if (entry1[0] == entry2[0])
                 return entry2[1] < entry1[1];
 
             else
                 return entry1[0] < entry2[0];
         });
 
    // Keep track of maximum
    // endurance value in right side
    int ma = 0;
 
    vector<int> res;
 
    // Traverse the array players
    for (int i = n - 1; i >= 0; i--) {
 
        // If current endurance
        // value is smaller than
        // max then we will
        // increment the count
        int id = qualities[i][2];
        if (qualities[i][1] < ma) {
 
            // Adding player
            // to the final array
            res.push_back(id);
 
            int q1 = qualities[i + 1][0] - qualities[i][0];
            int q2 = ma - qualities[i][1];
 
            // Increase the count
            count++;
        }
 
        // Else update max value
        ma = max(ma, qualities[i][1]);
    }
 
    return res;
}
 
// Driver Code
int main()
{
    vector<vector<int> > qualities
        = { { 1, 1, 0 }, { 2, 2, 1 }, { 3, 3, 2 } };
    vector<int> ans = CountOfPlayers(qualities);
 
    // Print total number of players
    // who need training
    cout << ans.size() << "\n";
 
    // Printing id of each player
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
 
   return 0;
}
 
    // This code is contributed by rakeshsahni

Java

// Java program for above approach
import java.io.*;
import java.util.*;
 
class GFG {
    private static Vector<Integer>
    CountOfPlayers(int[][] qualities)
    {
        int count = 0;
        int n = qualities.length;
 
        sort(qualities);
 
        // Keep track of maximum
        // endurance value in right side
        int max = 0;
 
        Vector<Integer> res
            = new Vector<Integer>();
 
        // Traverse the array players
        for (int i = n - 1; i >= 0; i--) {
 
            // If current endurance
            // value is smaller than
            // max then we will
            // increment the count
            int id = qualities[i][2];
            if (qualities[i][1] < max) {
 
                // Adding player
                // to the final array
                res.add(id);
 
                int q1
                    = qualities[i + 1][0]
                      - qualities[i][0];
                int q2 = max - qualities[i][1];
 
                // Increase the count
                count++;
            }
 
            // Else update max value
            max = Math.max(max, qualities[i][1]);
        }
 
        return res;
    }
 
    // Sort on the array according
    // to the above approach
    public static void sort(int arr[][])
    {
        // Using built-in sort
        // function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {
 
            @Override
            // Compare values according to columns
            public int compare(int[] entry1,
                               int[] entry2)
            {
 
                // If power value is equal
                // for both elements
                // Sort in descending order
                // according to endurance value
                if (entry1[0] == entry2[0])
                    return entry2[1] - entry1[1];
 
                else
                    return entry1[0] - entry2[0];
            }
        });
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[][] qualities
            = { { 1, 1, 0 },
                { 2, 2, 1 },
                { 3, 3, 2 } };
        Vector<Integer> ans
            = CountOfPlayers(qualities);
 
        // Print total number of players
        // who need training
        System.out.println(ans.size());
 
        // Printing id of each player
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i));
            System.out.print(" ");
        }
    }
}

Python3

# Python code to implement the approach
from functools import cmp_to_key
 
def cmp_sort(entry1,entry2):
 
    if (entry1[0] == entry2[0]):
        return entry2[1] - entry1[1]
 
    else:
        return entry1[0] - entry2[0]
 
def CountOfPlayers(qualities):
 
    count = 0
    n = len(qualities)
 
    qualities.sort(key = cmp_to_key(cmp_sort))
 
    # Keep track of maximum
    # endurance value in right side
    ma = 0
 
    res = []
 
    # Traverse the array players
    for i in range(n-1,-1,-1):
 
        # If current endurance
        # value is smaller than
        # max then we will
        # increment the count
        id = qualities[i][2]
        if (qualities[i][1] < ma):
 
            # Adding player
            # to the final array
            res.append(id)
 
            q1 = qualities[i + 1][0] - qualities[i][0]
            q2 = ma - qualities[i][1]
 
            # Increase the count
            count += 1
 
        # Else update max value
        ma = max(ma, qualities[i][1])
 
    return res
 
# Driver Code
qualities = [[1, 1, 0], [2, 2, 1], [3, 3, 2]]
ans = CountOfPlayers(qualities)
 
# Print total number of players
# who need training
print(len(ans))
 
# Printing id of each player
for i in range(len(ans)):
    print(ans[i] , end = " ")
 
# This code is contributed by shinjanpatra

C#

// C# program for above approach
 
using System;
using System.Collections.Generic;
 
public class GFG {
  private static List<int>
    CountOfPlayers(List<List<int>>  qualities)
  {
    int count = 0;
    int n = qualities.Count;
 
    qualities.Sort((entry1,entry2)=>{
      if (entry1[0] == entry2[0])
        return entry2[1] - entry1[1];
 
      else
        return entry1[0] - entry2[0];
    });
 
    // Keep track of maximum
    // endurance value in right side
    int max = 0;
 
    List<int> res
      = new List<int>();
 
    // Traverse the array players
    for (int i = n - 1; i >= 0; i--) {
 
      // If current endurance
      // value is smaller than
      // max then we will
      // increment the count
      int id = qualities[i][2];
      if (qualities[i][1] < max) {
 
        // Adding player
        // to the readonly array
        res.Add(id);
 
        int q1
          = qualities[i + 1][0]
          - qualities[i][0];
        int q2 = max - qualities[i][1];
 
        // Increase the count
        count++;
      }
 
      // Else update max value
      max = Math.Max(max, qualities[i][1]);
    }
 
    return res;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[,] qualities
      = { { 1, 1, 0 },
         { 2, 2, 1 },
         { 3, 3, 2 } };
    List<List<int>> qualities = new List<List<int>> ();
    for(int i = 0; i < qualities.GetLength(0); i++){
      List<int> l = new List<int>();
      l.Add(qualities[i, 0]);
      l.Add(qualities[i, 1]);
      l.Add(qualities[i, 2]);
      qualitie.Add(l);
    }
    List<int> ans
      = CountOfPlayers(qualitie);
 
    // Print total number of players
    // who need training
    Console.WriteLine(ans.Count);
 
    // Printing id of each player
    for (int i = 0; i < ans.Count; i++) {
      Console.Write(ans[i]);
      Console.Write(" ");
    }
  }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
 
      // JavaScript Program to implement
      // the above approach
      function CountOfPlayers(qualities)
      {
          let count = 0;
          let n = qualities.length;
 
          qualities.sort(function (entry1, entry2)
          {
 
              // If power value is equal
              // for both elements
              // Sort in descending order
              // according to endurance value
              if (entry1[0] == entry2[0])
                  return entry2[1] - entry1[1];
 
              else
                  return entry1[0] - entry2[0];
          })
 
          // Keep track of maximum
          // endurance value in right side
          let ma = 0;
 
          let res = [];
 
          // Traverse the array players
          for (let i = n - 1; i >= 0; i--) {
 
              // If current endurance
              // value is smaller than
              // max then we will
              // increment the count
              let id = qualities[i][2];
              if (qualities[i][1] < ma) {
 
                  // Adding player
                  // to the final array
                  res.push(id);
 
                  let q1 = qualities[i + 1][0] - qualities[i][0];
                  let q2 = ma - qualities[i][1];
 
                  // Increase the count
                  count++;
              }
 
              // Else update max value
              ma = Math.max(ma, qualities[i][1]);
          }
 
          return res;
      }
 
      // Driver Code
 
      let qualities
          = [[1, 1, 0], [2, 2, 1], [3, 3, 2]];
      let ans = CountOfPlayers(qualities);
 
      // Print total number of players
      // who need training
      document.write(ans.length + '<br>');
 
      // Printing id of each player
      for (let i = 0; i < ans.length; i++) {
          document.write(ans[i] + " ");
      }
 
  // This code is contributed by Potta Lokesh
  </script>
Producción

2
1 0

Complejidad de tiempo: O (NlogN), donde N es el tamaño de la array.

Complejidad espacial: O(1).

Publicación traducida automáticamente

Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *