fbpx

Problema #1373 – Reactivi – Rezolvari PBInfo

0

Enunt

Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia.
Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius).

Cerința

Scrieţi un program care să determine numărul minim de frigidere necesare pentru stocarea reactivilor chimici.

Date de intrare

Fişierul de intrare reactivi.in conţine:

  • pe prima linie numărul natural N, care reprezintă numărul de reactivi;
  • pe fiecare dintre următoarele N linii se află min max (două numere întregi separate printr-un spaţiu); numerele de pe linia x+1 reprezintă temperatura minimă, respectiv temperatura maximă de stocare a reactivului x.

Date de ieșire

Fişierul de ieşire reactivi.out va conţine o singură linie pe care este scris numărul minim de frigidere necesar.

Restricții și precizări

  • 1 <= N <= 8000
  • -100 <= minx <= maxx <= 100 (numere întregi, reprezentând grade Celsius), pentru orice x de la 1 la N
  • un frigider poate conţine un număr nelimitat de reactivi
#include <bits/stdc++.h>
using namespace std;

ifstream in("reactivi.in");
ofstream out("reactivi.out");

struct reactive {
    int mini, maxi;
} v[8005];

int n;

bool cmp(reactive a, reactive b) {
    if(a.maxi == b.maxi) {
        return a.mini < b.mini;
    }
    return a.maxi < b.maxi;
}

void solve() {
    sort(v + 1, v + 1 + n, cmp);

    int fridge = 1, ind = 1;
    for(int i = 2; i <= n; i++) {
        if(v[ind].maxi < v[i].mini) {
            fridge++;
            ind = i;
        }
    }
    out << fridge;
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++) {
       in >> v[i].mini >> v[i].maxi;
    }
    solve();
    return 0;
}

 

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More