¡Es hora del examen final en algoritmos y estructuras de datos!
Edsger preparó N juegos de problemas. Cada conjunto consta de problemas en una secuencia de dificultad creciente; el i-ésimo conjunto puede ser descrito por dos enteros Ai y Bi (Ai≤Bi), lo que denota que este conjunto contiene problemas con dificultades Ai, Ai+1…, Bi. Entre todos los problemas de todos los conjuntos, se garantiza que no hay dos problemas con la misma dificultad.
Este semestre Edsger tiene que probar Mestudiantes. Quiere evaluar a cada estudiante con exactamente un problema de uno de sus conjuntos. No hay dos estudiantes que puedan resolver exactamente el mismo problema, por lo que cuando Edsger evalúa a un estudiante con algún problema, ya no puede usar ese problema. A través de innumerables conferencias, ejercicios y proyectos, Edsger ha calculado que el estudiante número j tiene un nivel de habilidad Sj y quiere darle a ese estudiante un problema con dificultad Sj. Desafortunadamente, esto no siempre es posible, ya que es posible que Edsger no haya preparado un problema de esta dificultad, o que ya le haya planteado este problema a algún otro estudiante anteriormente. Por tanto, Edsger elegirá para el estudiante j-ésimo un problema de dificultad Pj, de forma que |Pj−Sj| es mínimo y no se le dio una pregunta de dificultad Pj a ninguno de los estudiantes antes del j-ésimo estudiante. En caso de empate, Edsger siempre elegirá el problema más fácil.
Como hacer un seguimiento de todos los problemas puede ser bastante complicado, ¿puedes ayudar a Edsger y determinar qué problemas debe dar a todos sus alumnos?
O
Dado un rango de problema de array de N pares que tienen valores iniciales y finales como un rango de niveles de dificultad, y una array de tamaño M que indica el nivel de dificultad que cada estudiante puede intentar. La tarea es asignar un entero único X del rango del problema a cada entero del arreglo arr tal que | arr[i] – X | se minimiza. En caso de empate entre dos valores más cercanos a arr[i] , se debe elegir un valor de menor dificultad. Los valores de X deben asignarse a los estudiantes en su orden ya que no se puede asignar el mismo valor de X a más de un estudiante. Imprime elValor X asignado a cada alumno.
Ejemplo:
Entrada: N = 5, M = 4, arr = [14, 24, 24, 4], rango de problemas = [[1, 2], [6, 7], [9, 12], [24, 24], [ 41, 50]]
Salida: 12 24 11 2
Explicación: los valores que se pueden asignar a los estudiantes son {1, 2}, {6, 7}, {9, 10, 11, 12}, {24}, {41 , 42, 43, 44, 45, 46, 47, 48, 49, 50} 12 se asigna al primer alumno que puede intentar preguntas de nivel de dificultad 14, ya que es el más cercano al 14. 24 es el más cercano al 24. El siguiente alumno puede también intente la pregunta de dificultad 24 pero la 24 del rango ya está elegida y la siguiente más cercana es la 11. 2 y 6 es la más cercana al último estudiante de dificultad 4, ya que 2 y 6 están igualmente cerca de 4, preguntas más fáciles de dificultad 2 es asignado.Entrada: N = 1, M = 1, arr = [24], problemRange =[[42, 42]]
Salida: 42
Enfoque: el problema dado se puede resolver siguiendo los pasos a continuación:
- Use un mapa para almacenar el inicio de los rangos como claves y el final de los rangos como valores
- Iterar la array y para cada elemento en ella encontrar su límite inferior en el mapa
- Son posibles dos casos: Lower_bound devolverá el iterador que apunta a la clave que será igual a arr[i] o la clave que es mayor que arr[i]
- digamos que el iterador provisto por lower_bound sea él y pre sea un iterador justo antes de él ( pre será igual a él cuando = mp.begin () )
- Ya sea pre.first<=arr[i]<=pre.second o it.first<=arr[i]<=it.second será verdadero. arr[i] estará en la sección de avance o en la sección de retroceso de este rango
- cada vez que se asigna un valor al arr[i], el rango anterior se elimina del mapa y se agrega un nuevo rango como se muestra en la imagen
- Se agregan dos rangos nuevos o se agrega un rango nuevo como los casos que se muestran en las imágenes a continuación:
Solo un elemento está presente en el rango, por lo que se elimina y no se agrega un nuevo rango
arr[i] es igual a cualquiera de los rangos
Se elimina el rango anterior y se agregan dos nuevos rangos en el mapa
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
void solve(long long int N, long long int M,
vector<pair<long long int,
long long int> >
problemRange,
vector<long long int> arr)
{
// Store the problem range in a map
map<long long int, long long int> mp;
for (long long int i = 0; i < N; i++) {
long long int a, b;
a = problemRange[i].first;
b = problemRange[i].second;
mp[a] = b;
}
vector<long long int> ans(M);
for (long long int i = 0; i < M; i++) {
auto it = mp.lower_bound(arr[i]);
auto pre = it;
if (it != mp.begin())
pre--;
// If answer lies in a valid range
if (pre->first <= arr[i]
&& arr[i] <= pre->second) {
ans[i] = arr[i];
long long int st = pre->first,
end = pre->second;
mp.erase(pre);
long long int left = arr[i] - 1,
right = arr[i] + 1;
if (st <= left) {
mp[st] = left;
}
if (end >= right) {
mp[right] = end;
}
}
// If answer is not in a valid range
else {
long long int op1 = pre->second,
op2 = it->first;
if (abs(arr[i] - op1) <= abs(arr[i] - op2)) {
ans[i] = op1;
long long int st = pre->first,
end = op1 - 1;
mp.erase(pre);
if (st <= end)
mp[st] = end;
}
else {
ans[i] = op2;
long long int st = it->first + 1,
end = it->second;
mp.erase(it);
if (st <= end)
mp[st] = end;
}
}
}
for (auto it : ans)
cout << it << " ";
cout << endl;
}
// Driver code
int main()
{
long long int N, M;
N = 5;
M = 4;
// Student difficulty level
vector<long long int> arr = { 14, 24, 24, 4 };
vector<pair<long long int,
long long int> >
problemRange = { { 1, 2 },
{ 6, 7 },
{ 9, 12 },
{ 24, 24 },
{ 41, 50 } };
solve(N, M, problemRange, arr);
return 0;
}
12 24 11 2
Complejidad temporal: MLog(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por satyamkant2805 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA