1203 - Argus.cpp

/**
En el siguiente caso se producen varias condiciones "especiales",
Para verficar si tu programa etsa bien

Input:
Register 1050  50
Register 2010  10
Register 2555   5
Register 2345   5
#
8
Output:
2345
2555
2010
2345
2555
2345
2555
2010


La idea basica consiste en hacer algo muy ad-hoc añadiendo a una cola de prioridad(PQ) la actividad con su tiempo t,
depues imprimarla en orden inverso y listo. 
Ojo:No es la solución optima, se puede mejorar evitando recorrer toda la PQ para despues meterle en una pila 
y volver a recorrer esa pila para imprimir la solución

**/

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
using namespace std;

typedef pair <int,int> registro;

priority_queue<registro> PQ;
stack<registro> Q;
vector <registro> V;
string s;


int id,t,q,r;
long long int res;

int main(){
    cin>>s;
    while(s!="#"){
        scanf("%d %d",&id,&t);
        V.push_back(make_pair(t,id));
        cin>>s;
    }
    sort(V.begin(),V.end());
    scanf("%d",&q);
    int aux=1;
    while(r<q){
        int maxi=0;
        maxi=V[0].first*(aux+1);//Esto es importante para asegurarnos que tenemos los menores valores posibles
        for(int i=0;i<V.size()   ;i++){
            PQ.push(make_pair(V[i].first*aux,V[i].second));
            /**metemos todos porque se pude dar que V[i].first*aux <=V[i-1].first*(aux+1), pero no aumentamos r porque se puede producir
                que V[i].first*aux >V[i-1].first*(aux+1)
            **/

            if(V[i].first*aux<=maxi)

                r++;
        }
        aux++;

    }

    while(!PQ.empty()){
       // printf("%d\n",PQ.top().second);
        Q.push(PQ.top());
        PQ.pop();
    }

    while(!Q.empty()&&q--){
        printf("%d\n",Q.top().second);
        Q.pop();
    }

    return 0;

}