0

Estoy intentando resolver el siguiente problema:

"La Unidad Curiosa de Monitorización (UCM) se encarga de leer los datos proporcionados por una serie de sensores y enviar con cierta periodicidad los datos obtenidos y procesados a los usuarios que se han registrado previamente.

La UCM admite que los usuarios se registren proporcionando un Identificador, un número entre 10^3 y 10^9 que identifica de forma única al usuario, y un Periodo, el intervalo de tiempo que transcurrirá entre dos envíos consecutivos de información a ese usuario (entre 1 y 5.000). Es decir, cuando hayan pasado Periodo segundos desde que el usuario se registró, este recibirá la información de la UCM por primera vez; y después recibirá la información cada Periodo segundos.

Acaban de registrarse varios usuarios, todos con identificadores dintintos. ¿Podrías decir a quiénes irán dirigidos los K primeros envíos de información? Si dos o más usuarios tienen que recibir la información al mismo tiempo, los envíos se realizan en orden creciente de sus identificadores de usuario."

ENTRADA: primero especificamos el nº de usuarios que se supone, se registran a la vez. Seguimos con el ID y la frecuencia(segundos por ejemplo) con la que recibirán la informacíon de cada uno. Una vez acabamos de introducir los datos de todos los usuarios, introducimos el nº de envíos que el sistema realizará cuyo destinatario deseamos conocer.

SALIDA: ID de los usuarios que recibirán la información según la frecuencia introducida de cada uno.

Tras crear el algoritmo que lo resolviera, el problema que tengo es que según el nº de envíos que especifiques, la salida es correcta o no.

Aclaración: esto anterior quiere decir que, por ejemplo, con un nº de envios igual a 50 puede que no obtengamos correctamente la secuencia de usuarios que recibirán los envíos pero con 51 si, ya que, con un envío mas, al insertar en la cola de prioridad otro par mas, se colocará en la posicion correcta y obtendremos la salida correctamente pero sin ese envío no.

Ejemplo de entradas:

2 1000 2 1001 1 2. Salida: 1001 1001. No proporciona la salida correcta.

2 1000 2 1001 1 3. Salida: 1001 1000 1001. Si proporciona la salida correcta.

El código es el siguiente realizado en c++:

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

const int CASO_ESPECIAL= 0;

int main(){
    int usuarios;
    int i, n_envios;

    while(scanf("%d", &usuarios)>0){
        if(usuarios==CASO_ESPECIAL)
            return 0;

        std::pair<int, int> datos[usuarios];
        int frecs[usuarios];

        for(i=0; i<usuarios; i++){
            scanf("%d", &datos[i].second);
            scanf("%d", &datos[i].first);
            frecs[i]= datos[i].first;
        }

        sort(datos, datos+usuarios);
        std::sort(frecs, frecs+usuarios);

        scanf("%d", &n_envios);


        std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >, 
                            std::greater<std::pair<int,int> > > resultado;

        i=0;

        while(n_envios){
            if(datos[i].first < datos[(i+1)%usuarios].first){               
                resultado.push(datos[i]);
                datos[i].first+=frecs[i];
                i=0;
                n_envios--;

            }else if(datos[i].first==datos[(i+1)%usuarios].first){
                    resultado.push(datos[i]);
                    datos[i].first+=frecs[i];
                    i=(i+1)%usuarios;
                    n_envios--;

            }
            else{
                i=(i+1)%usuarios;
            }
        }

        while(!resultado.empty()){
            printf("%d\n", resultado.top().second); 
            resultado.pop();
        }

        printf("----\n");
    }

    return 0;
}
14
  • Estaría bien que indicases qué es lo que falla de tu código... ¿Tenemos que depurarlo nosotros y resolver todos los errores que vayamos encontrando?
    – eferion
    el 17 jul. 2017 a las 13:35
  • No lo he explicado pero el programa utiliza librerias de c y c++ por diversos motivos que no conviene explicar ahora.. el 17 jul. 2017 a las 13:36
  • No te confundas... estás usando librerías de C++ todo el rato. Los estándares de C y C++ son distintos y hay cosas en C que no son están permitidas en C++ (y viceversa) luego no, las librerías de C no son librerías de C++ aunque se llamen igual. Estás programando en C++
    – eferion
    el 17 jul. 2017 a las 13:37
  • Gracias por la aclaración eferion, como se puede ver soy aún un novato.. :S. También soy novato escribiendo dudas de programación, explico el problema que tengo: cuando compilas el programa y empiezas a probar con distintos casos de prueba, normalmente obtienes la salida esperada pero cuando insertas un número de envíos el cual "se queda corto", la salida no es la esperada, por ejemplo con la siguiente entrada: 2 1000 2 1001 1 50. el 17 jul. 2017 a las 13:43
  • No te estaba regañando. Por cierto, esas aclaraciones deberían formar parte de la pregunta. Por favor, edítala y añade esa información.
    – eferion
    el 17 jul. 2017 a las 13:46

2 respuestas 2

2
std::pair<int, int> datos[usuarios];

A esta estructura se la conoce como VLA (Variable Length Array) y lamento decirte que no es algo legal en C++. Algunos compiladores y extensiones lo soportan, pero no es conforme al estándar y es mejor prevenir su uso. Puedes llevarte desagradables sorpresas al actualizar el compilador o al llevarte el código a una máquina diferente.

Por otro lado me da la sensación de que piensas que priority_queue es capaz de detectar que estás modificando el valor de un elemento interno para reorganizar la lista... y no es así. Para poder detectar esos cambios std::pair tendría que avisar a std::vector de que se ha producido un cambio y este a su vez se lo debería propagar a std::priority_queue y nada de eso está programado por ningun lado (ni hay forma de hacerlo).

Lo que tienes que hacer es reorganizar la lista cada vez que realizas un envío.

Las prioridades vienen dadas por:

  1. Periodo más bajo
  2. ID de usuario más baja

Manejar std::pair para cosas así me parece un poco aberrante porque hay que estar recordando todo el rato qué dato se almacena en pair.first y qué dato hay en pair.second... y si los mezclas se lía cosa mala... con lo sencillo que resulta crear una estructura de datos:

class Usuario
{
  int id;
  int periodo;
  int tiempo;

public:


  Usuario(int periodo, int id)
    : periodo(periodo), id(id), tiempo(periodo)
  { }

  void Atendido()
  { tiempo += periodo; }

  int Id() const
  { return id; }

  int Periodo() const
  { return periodo; }

  int Tiempo() const
  { return tiempo; }

  bool operator<(Usuario const& otro) const
  {
    return std::tie(tiempo,id) < std::tie(otro.tiempo,otro.id);
  }
};

Esta estructura no solo almacena los datos del usuario, sino que es capaz de llevar la cuenta del tiempo. Adicionalmente incorpora una implementación del operador de comparación para facilitar la ordenación.

Por otro lado, lo más razonable dado el enunciado es tirar de std::vector para almacenar la lista de usuarios:

std::vector<Usuario> usuarios;

Rellenar la lista es algo trivial, aunque quedaría mejor si pasamos a usar la IO propia de C++:

while( true )
{
  int numUsuarios;
  // std::cout << "Numero de usuarios: ";
  if( !(std::cin >> numUsuarios) || numUsuarios == 0)
    break;

  std::vector<Usuario> usuarios;
  for( int i=0; i<numUsuarios; i++ )
  {
    int periodo, id;
    std::cin >> periodo >> id;
    usuarios.push_back(Usuario(id,periodo));
  }

Ahora hay que realizar n envios. Hay que tener en cuenta que cada envío requiere reordenar la lista

int envios;
// std::cout << "Numero de envios: ";
std::cin >> envios;

while( envios-- )
{
  std::sort(usuarios.begin(),usuarios.end());

  Usuario& usuario = usuarios.front(); // Recuperamos el primer elemento
  std::cout << usuario.Id() << '\n';
  usuario.Atendido(); // Lo marcamos como atendido (se incrementa su tiempo)
}

Puedes ver el ejemplo en funcionamiento en wandbox

En base a un comentario:

Acabo de aprender bastante por la respuesta que has aportado, incluso es la solución a la pregunta planteada pero el problema que aún sigo teniendo, es que la solución aportada es "lenta" ya que requiere ordenar el vector en cada envío. Este problema está en la siguiente página de retos de programación: aceptaelreto.com/problem/statement.php?id=351&cat=20 y a la hora de evaluar el problema, se obtiene el error de que el juez online tarda demasiado tiempo en comprobar todos los casos de prueba, por eso he intentado esas soluciones tan "raras". Gracias.

Bien, con un par de adaptaciones que he comentado (ver comentarios aunque sea redundante) los resultados son los siguientes:

8   143128  eferion C++ 0.396   1820    Hace 2 minutos

Una solución que entra dentro del top10 sin esforzarme demasiado con el algoritmo. ¿Se puede mejorar? por supuesto que sí, pero para ser una solución cocinada en menos de media hora creo que el resultado es bastante aceptable.

2
  • Acabo de aprender bastante por la respuesta que has aportado, incluso es la solución a la pregunta planteada pero el problema que aún sigo teniendo, es que la solución aportada es "lenta" ya que requiere ordenar el vector en cada envío. Este problema está en la siguiente página de retos de programación: aceptaelreto.com/problem/statement.php?id=351&cat=20 y a la hora de evaluar el problema, se obtiene el error de que el juez online tarda demasiado tiempo en comprobar todos los casos de prueba, por eso he intentado esas soluciones tan "raras". Gracias. el 17 jul. 2017 a las 15:24
  • @JuaneGarciaMartinez mi intención no es darte la respuesta óptima sino presentarte una solución. Si lo piensas un poco te darás cuenta de que no es necesario reordenar todo el vector sino únicamente los primeros n elementos (n sería la nueva posición del usuario al que le has enviado el dato). Otra mejora la consigues llamando a reserve() del vector para que no tenga que llamar a realloc cada vez que se metan elementos en el mismo... en cuanto a la IO, si desincronizas cin/cout con stdin/stdout conseguirás que las lecturas y escrituras sean más rápidas que las homólogas en C
    – eferion
    el 17 jul. 2017 a las 15:38
0

Tras bastante tiempo detrás de este problema, y gracias a la recomendación de eferion, he conseguido resolver el problema en tiempo razonable, introduciendo en su código los siguientes cambios: usando una priority_queue<Usuario> mostrando el elemento top de la cola, "sacando" dicho elemento, actualizándolo (método Atendido()), y volviéndolo a meter, el n° de envíos especificado como entrada.

Dejo el código para una mayor comprensión:

#include <iostream>
#include <tuple>
#include <queue>

class Usuario {
    int periodo;
    int id;
    int tiempo;

public:
    Usuario(){
        periodo=id=tiempo=0;
    }

    Usuario(int periodo, int id)
    : periodo(periodo), id(id), tiempo(periodo) {
    }

    void Atendido() {
        tiempo += periodo;
    }

    int Id() const {
        return id;
    }

    int Periodo() const {
        return periodo;
    }

    int Tiempo() const {
        return tiempo;
    }

    bool operator<(Usuario const& otro) const {
        return std::tie(tiempo, id) < std::tie(otro.tiempo, otro.id);
    }

    bool operator>(Usuario const& otro) const {
        return std::tie(tiempo, id) > std::tie(otro.tiempo, otro.id);
    }
};

int main() {
    int numUsuarios, periodo, id, envios;
    Usuario usuario;

    while (true) {
        if (!(std::cin >> numUsuarios) || numUsuarios == 0)
            break;

        std::priority_queue<Usuario, std::vector<Usuario>, std::greater<Usuario> > usuarios;
        for (int i = 0; i < numUsuarios; i++) {
            std::cin >> periodo >> id;
            usuarios.push(Usuario(id, periodo));
        }

        std::cin >> envios;

        while (envios--) {
            usuario = usuarios.top();
            std::cout << usuario.Id() << '\n';
            usuarios.pop();
            usuario.Atendido();
            usuarios.push(usuario);
        }
        std::cout << "----\n";
    }
}

Muchas gracias! :D

1
  • 2
    Podrías aportar algo de código para que veamos la solución más claramente? Si esta es la solución a tu problema, por favor, considera marcarla como respuesta aceptada para que la pregunta quede cerrada.
    – Muriano
    el 18 jul. 2017 a las 7:12

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.