// OBI 2023 - Fase 2 // UPA - Solução O(N log N) gulosa usando sets // Mateus Bezrutchka // // Algoritmo guloso: processamos os ônibus ordenados por ordem de chegada. // Toda vez que chega um ônibus, ele pega qualquer vaga disponível, // ou criamos uma se essa vaga não existe. // É possível provar, por contradição via argumento de troca, que esse // algoritmo sempre cria o mínimo possível de vagas. // #include #include #include #include using namespace std; const int MAXN = 100100; int n; pair onibus[MAXN]; multiset tempo_disp; // tempos em que as vagas ficarão disponíveis novamente int num_vagas; // quantas vagas criamos até agora void estacione_onibus(int chegada, int partida) { if (*tempo_disp.begin() > chegada) { // nenhuma vaga disponivel no momento de chegada num_vagas++; tempo_disp.insert(partida); } else { // posso usar qualquer vaga disponivel no momento; // em particular, posso usar a primeira do set int tempo_old = *tempo_disp.begin(); tempo_disp.erase(tempo_disp.find(tempo_old)); tempo_disp.insert(partida); } } int min_num_vagas() { // começamos com uma vaga, disponivel no tempo 0 tempo_disp.insert(0); num_vagas = 1; sort(onibus, onibus + n); // ordena por ordem de chegada for (int i = 0; i < n; i++) { estacione_onibus(onibus[i].first, onibus[i].second); } return num_vagas; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &onibus[i].first, &onibus[i].second); } int resp = 20 * min_num_vagas(); printf("%d\n", resp); return 0; }