// OBI 2023 - Fase 2 // UPA - Solução O(N log N) com line sweep // Mateus Bezrutchka // // Perceba que o problema é equivalente a, dados N intervalos na reta (o período // que cada ônibus ficará estacionado), calcular o número máximo de intervalos // que se intersectam -- podemos provar, via um argumento guloso, que se K é o // máximo de intervalos que se intersectam, então conseguimos estacionar todos os // ônibus usando K vagas, sempre alocando o ônibus que chega antes (intervalo mais // à esquerda) para qualquer vaga disponível. // // Esse novo problema, dos intervalos que se intersectam, pode ser resolvido // com a técnica de "line sweep" -- criamos "eventos" em pontos da reta, indicando // que um intervalo começa (entra) ou termina (sai) nesse ponto (assim, temos // exatamente dois eventos por intervalo). Processamos esses eventos da esquerda // para a direita, mantendo um contador de quantos intervalos estão ativos // (intervalos que começaram mas não terminaram) na coordenada atual. // #include #include #include using namespace std; const int MAXN = 100100; int n; pair eventos[2 * MAXN]; // par (coordenada; 0 pra entrada e 1 pra partida) int min_num_vagas() { sort(eventos, eventos + 2 * n); // ordena por coordenada int intervalos_ativos = 0; int max_intervalos_ativos = 0; for (int i = 0; i < 2 * n; i++) { if (i > 0 && eventos[i - 1].first != eventos[i].first) { // acabei de mudar de coordenada, preciso considerar a contagem anterior max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos); } if (eventos[i].second == 0) { intervalos_ativos++; } else { intervalos_ativos--; } } // faltou considerar a ultima contagem max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos); return max_intervalos_ativos; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int chegada, partida; scanf("%d %d", &chegada, &partida); eventos[2 * i] = make_pair(chegada, 0); eventos[2 * i + 1] = make_pair(partida, 1); } int resp = 20 * min_num_vagas(); printf("%d\n", resp); return 0; }