Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Numărul minim de peroane pentru o gară în C++

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Știind momentele venirii și plecării ale unor trenuri într-o gară, să se determine numărul minim de peroane pe care trebuie să le aibă gara pentru ca fiecare tren să poată să staționeze.

Exemplu: Să presupunem că vin n = 5 trenuri la orele:

  1. 08:0008:15
  2. 08:2009:00
  3. 08:4509:15
  4. 08:5509:15
  5. 09:2009:25

Atunci, sunt necesare minimum trei peroane pentru ca toate trenurile să poată staționa la gară (în intervalul 08:5509:00, vor fi trei trenuri în gară simultan).

Pentru datele de intrare, vom citi:

5
800 815
820 900
845 915
855 915
920 925

Explicarea algoritmului

Problema noastră se reduce la a ne asigura că în momentul în care un număr maxim de trenuri sunt în gară, toate acestea au un loc de staționare asigurat. În exemplul nostru, trebuia să ne asigurăm că sunt minimum trei peroane, pentru a asigura staționarea trenurilor 2, 3 și 4 în intervalul 08:5509:00. Putem observa intervalul în imaginea de mai jos (cu roșu este intervalul căutat):

https://i.ibb.co/0nhRvkz/image.png

Cum găsim intervalul de timp în care sunt cele mai multe trenuri în gară?

Să contorizăm numărul de trenuri din gară. La început, sunt 0 trenuri. După venirea primului tren, va fi 1 tren. La plecarea acestuia, vor fi iarăși 0 trenuri. Când vine trenul al doilea, iarăși va fi 1 tren. Când vine al treilea tren, vor fi 2 trenuri. Când vine al patrulea tren, vor fi 3 trenuri (maximul). Și așa mai departe.

Observăm că, dacă ordonăm momentele venirii și plecării în ordine cronologică și considerăm momentele venirii +1 și cele de plecare -1, numărul maxim de trenuri în gară este maximul dintre valorile contorului pe parcursul parcurgerii momentelor. În exemplu, contorul ia valorile 0, 1, 0, 1, 2, 3, 2, 1, 0, 1, 0, maximul lor fiind 3.

Cum ordonăm momentele de venire și de plecare?

Există multe metode, cele mai elegante folosind structuri. În cazul nostru, ne vom folosi de doi vectori: timp și tip, cu semnificația:

  • timp[i] reprezintă momentul celui de-al i-lea eveniment (evenimentul poate fi o venire sau o plecare de tren);
  • tip[i] reprezintă tipul celui de-al i-lea eveniment:
    • dacă tip[i] = 1, atunci un tren vine;
    • altfel, dacă tip[i] = -1, atunci un tren pleacă.

După ce citim aceste date, le vom sorta folosind un algoritm de sortare cunoscut. După care, folosind observația de mai devreme, putem să calculăm contorul și să luăm cea mai mare valoare posibilă.

Rezolvare în C++

Iată rezolvarea în C++, fără să folosim structuri:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n; //numărul de trenuri
    int timp[101]; //timpul în care vin trenurile
    int tip[101]; //tipurile trenurilor
    int nrev = 0; //numărul evenimentelor; pentru fiecare dintre cele n trenuri sunt 2 evenimente, așadar nrev = 2 * n după citire
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int venire, plecare;
        cin >> venire >> plecare;
        //Băgăm evenimentul de venire
        nrev++;
        timp[nrev] = venire;
        tip[nrev] = 1;

        //Băgăm evenimentul de plecare
        nrev++;
        timp[nrev] = plecare;
        tip[nrev] = -1;
    }

    //Sortăm evenimentele în ordine cronologică (adică în funcție de *timp*)
    //Avem grijă să interschimbăm atât valorile din timp, cât și din tip
    for(int i = 1; i <= nrev; i++) {
        for(int j = i + 1; j <= nrev; j++) {
            if(timp[i] > timp[j]) {
                int aux = timp[i];
                timp[i] = timp[j];
                timp[j] = aux;
                aux = tip[i];
                tip[i] = tip[j];
                tip[j] = aux;
            }
        }
    }

    //În acest moment, evenimentele sunt în ordine cronologică
    //Parcurgem evenimentele pe rând și contorizăm, luând maximul
    //Observăm că nu ne mai trebuie timpul, ci doar tipul evenimentelor
    int contor = 0, raspuns = 0;
    for(int i = 1; i <= nrev; i++) {
        contor += tip[i]; //contor crește sau scade cu 1
        if(contor > raspuns) { //actualizăm răspunsul dacă contorul are o valoare maximă nouă
            raspuns = contor;
        }
    }
    cout << raspuns;
    return 0;
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Ce înseamnă endl în C++?Verifică dacă un caracter este literă în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorIndicatorul lui Euler în C++Factorialul unui număr în C++Maximul și minimul a trei valori în C++Verificarea unui an bisect în C++Complexitatea unui algoritm (timp și spațiu) în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăNumărul de apariții al unui număr într-un vector în C++Codul ASCII (tabel complet)Al N-lea termen Fibonacci în C++Suma elementelor unui vector recursiv în C++Transformarea unei litere mari în literă mică în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortCăutare binară în C++Valoarea absolută (modulul) unui număr în C++Numărul de cifre ale factorialului unui numărNumărul de divizori al unui număr în C++Bordarea unei matrice în C++Verificare dacă un număr este palindrom în C++Divide et Impera (metodă de programare C++)Combinatorică în C++: permutări, aranjamente, combinări și alteleTipul struct în C++. Ce sunt structurile de date neomogeneFuncții predefinite în C++ (matematice, șiruri de caractere)Inversarea unui vector în C++Verificare dacă șir de caractere este palindrom în C++Instrucțiunea de decizie în C++: if, else, switch, caseTransformarea unui număr din baza 10 în baza 2 în C++Rădăcina cubică a unui număr în C++ (cube root)Afișarea elementelor unui vector recursiv în C++Șiruri de caractere în C++. Tot ce trebuie să știiNumărul de divizori primi ai unui număr în C++Verifică dacă un număr aparține șirului Fibonacci în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Citește un șir de caractere cu spații în C++Verifică dacă trei puncte sunt coliniare C++Operații cu numere mari în C++ - Toate funcțiile explicateAria unui triunghi folosind coordonatele acestora în C++Verifică dacă un număr dat este o putere de 2 în C++Prima cifră a unui număr în C++Cifra maximă a unui număr recursiv în C++Vectorii în C++: citire și afișareAflarea sumei primelor N sume GaussSuma numerelor naturale dintr-un interval dat în C++Al N-lea termen dintr-o progresie aritmeticăCifrele unui număr. Prelucrarea cifrelor unui număr în C++Instrucțiunea do while (structuri repetitive)Maximul și minimul unui vector în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Instrucțiunea for (structuri repetitive)Cifra maximă și minimă a unui număr în C++CMMDC recursiv a două numere naturale în C++Copiuțe: Cifrele unui numărInterclasarea a doi vectori în C++Vectorii în C++: declarare și parcurgereAfișarea divizorilor primi ai unui număr în C++Radicalul unui număr în C++ (rădăcina pătrată)Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Instrucțiunea continue (structuri repetitive)Ciurul lui Eratostene în C++Maximul și minimul a n valori în C++Transformarea unei litere mici în literă mare în C++Recursivitate în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicNumere triunghiulare. Verificarea unui număr triunghiularCel mai frecvent element dintr-un șir în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Distanța dintre două puncte în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Maximul și minimul a două valori în C++Cea mai lungă secvență de elemente crescătoare în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Verificare număr prim în C++ (Clasa a IX-a)Suma divizorilor unui număr în C++Comentarii în C++Află secolul unui an citit de la tastatură în C++Cum să afișezi partea întreagă a unui număr real în C++Aria și circumferința unui cerc în C++Pointer în C++. Variabile de tipul char * (char steluță)Structuri repetitive (while, do while, for, etc)Mediana unui șir de valori în C++Cel mai semnificativ bit în C++Verifică dacă o literă este vocală în C++Cel mai puțin semnificativ bit în C++Verifică dacă o literă este mică sau mare în C++Do while vs while în C++ - Care e diferența?Câte numere naturale sunt într-un interval dat? (C++)Inversarea unui șir de caractere în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleSuma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cum să calculezi instant 2 la puterea N în C++Ce este o funcție void în C++?Transformarea unui număr din baza 2 în baza 10 în C++Ce este o variabilă unsigned în C++?Ce înseamnă variabilă globală și locală în C++?Șirul lui Fibonacci în C++Citirea și afișarea matricelor în C++Numărul minim de peroane pentru o gară în C++Verifică dacă un număr este par sau impar fără modulo în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Oglinditul recursiv al unui număr în C++Vectori de frecvență (de apariții) în C++Calculul combinărilor de n luate câte k (nCk) în C++Cel mai mic număr cu suma cifrelor N în C++Al N-lea termen dintr-o progresie geometricăNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cum să citești și să afișezi în fișiere în C++Instrucțiunea while (structuri repetitive)Numărul permutărilor în C++ (formula permutărilor)Numărul combinărilor în C++ (formula combinărilor)Tipuri de date în C++: numere întregi, reale, caractere și alteleSuma 1 + 2 + 3 + ... + N în C++Cifra de control a unui numărInterschimbarea a două variabile în C++ (3 metode)Matrice pătratice în C++. Diagonala principală și secundarăGenerarea șirului Fibonacci generalizat în C++Funcții în C++. Ce sunt subprogrameleVerifică dacă un caracter este cifră în C++Instrucțiunea break (structuri repetitive)Oglinditul unui număr în C++Materia pentru olimpiada de informatică - tot ce trebuie să știi

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont