Acolchados de Clase

Toppers de la Clase – es un problema de codificación entrevista se produjo en la ronda de codificación de D.E.Shaw . A continuación, vamos a implementar su solución, junto con el ejemplo y algoritmo.

Planteamiento del problema:

Hay una clase de N estudiantes y la tarea es encontrar la parte superior K- marcas goleadores. Escribir un programa que va a imprimir el índice de los primeros de la clase, que será el mismo que el índice del estudiante en la matriz de entrada (indexación basada en el uso 0). En primer lugar imprimir el índice de los estudiantes que tienen calificaciones más altas a continuación, los estudiantes con la segunda más alta y así sucesivamente. If hay más de un estudiantes que tienen mismas marcas y luego imprimir sus índices en orden ascendente.

de entrada Ejemplo:

Supongamos k = 2 y los estudiantes que tienen calificaciones más altas tienen índices 0 y 5 y estudiantes teniendo segunda marcas más altas tienen índices de 6 y 7 a continuación, la salida será 0 5 6 7.

    K=2
N=10
Marks are:
97 84 82 89 84 97 95 95 84 86
Output:
0 5 6 7, so there are four toppers for K=2

97 y 95 se ha de considerar. Hay cuatro estudiantes que tiene esto. Sus índices son 0 5 6 7 (por una marcas particulares if hay más de un estudiante, sus necesidades índices para imprimir en orden ascendente).

Solución:

estructura de datos utilizada:

  1. Conjunto (ordenados en la disminución de la moda)
  2. mapa (ordenada en la disminución de la moda)

Algoritmo:

  1. necesidad de almacenar las marcas en orden descendente manera ordenada.
  2. Las marcas son clave y que necesitan asignar índices de estudiantes al valor de clave. índices de mapeo While necesarios para ser mapeados en orden ascendente de la moda.
  3. impresión índices de claves K (marcas ya valoran ordenados en la disminución de la moda, por lo que la parte superior K teclas son de primera marcas K).

Implementación con las estructuras de datos utilizadas: registros

  1. declarar como un mapa.
    map<int, vector<int>, greater <int>> records;

    mapa = mapa ordenado generalmente ordenado en orden ascendente de la moda como por valor de clave mayor & lt; int & gt; se utiliza a fin de que desciende la moda.
    Aquí la llave es de tipo entero que se asigna a un vector de número entero. Es evidente que la clave está en las marcas y que se asigna a una lista de índices de estudiantes.

  2. números de declarar como un conjunto.
    set<int, greater<int>> numbers; 

    set = conjunto ordenado generalmente ordenado en orden ascendente de la moda como por valor del elemento mayor & lt; int & gt; se utiliza a fin de que desciende la moda.
    Aquí los elementos son las marcas que se almacenan de forma ordenada descendente.

  3. Después de la finalización de la toma de entrada, ambos registros y números están llenos de datas más como por mencionó anteriormente.

Consideremos el ejemplo de entrada por encima:

    K=2
N=10
Marks are:
97 84 82 89 84 97 95 95 84 86

Así que después de la finalización de la toma de entrada:

Records se parece a:

Toppers of Class - 4

Números ve así:

Toppers of Class - 5

K = 2, por lo que necesitamos para imprimir índices sólo para las marcas 97, 95

Así, los índices sean de impresión son: 0 5 6 7

Así que para imprimir:

For i =0: K
Set iterator tonumbers.begin() //points to 97
Advance iterator by i; //to point at ith mark from the top
Print the vector list associated with the key (marks) pointed to.
END FOR

implementación en C ++ para los primeros de la clase de

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
//n is no of students, k is the input K
cout<<"enter no of studentn";
scanf("%d",&n);
map<int,vector<int>,greater <int>> records;//declare records
set<int,greater<int>> numbers;//declare numbers
int no;
cout<<"enter the marks of the studentsn";
for(int i=0;i<n;i++){
cin>>no;
//for key value build the vector list
records[no].push_back(i);
//to avoid duplicate
if(numbers.find(no)==numbers.end())
numbers.insert(no); //insert marks to set
}
cout<<"enter Kn";
cin>>k; //input K
cout<<"Toppers are: ";
//printing the indices
for(int i=0;i<k;i++){
auto ij=numbers.begin();
advance(ij,i);
//printing the associated vector
for(auto it=records[*ij].begin();it!=records[*ij].end();it++){
printf("%d ",*it);
}
}
cout<<endl;
return 0;
}

salida

enter no of student
10
enter the marks of the students
97 84 82 89 84 97 95 95 84 86
enter K
2
Toppers are: 0 5 6 7


Deja un comentario

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