Question

Ajutor problema admitere va rog!

Answer 1

Explicatie :

Ne gandim la programul vacilor ca la un timeframe, ca la un fel de orar. Astfel, o paranteza dreapta deschisa reprezinta inceputul intervalului cand o vaca da lapte, iar o paranteza dreapta inchisa reprezinta sfarsitul intervalului cand o vaca da lapte.

Exemplul nostru devine :

[         [               ]           ]           [          ]

300   700    1000    1200      1500  2100

Intervalul maxim in care cel putin o vaca da lapte : intervalul maxim in care avem cel putin o paranteza deschisa.

Intervalul maxim in care nicio vaca nu da lapte : intervalul maxim in care avem nicio paranteza deschisa.

Fiecare element e reprezentat de o structura care contine ora si tipul elementului (inceput de interval sau sfarsit de interval). Ordonam cronologic toate aceste elemente in functie de ora. Apoi folosindu-ne de numarul de intervale deschise la orice moment cate vaci dau lapte in momentul respectiv.

Restrictii ale programului meu pe care problema nu le specifica: Se considera ca lucram cu ore intregi sau cu procente de ore (se accepta ore de tip 100,200,300,..., sau ora 350 reprezinta 350% dintr-o ora (3 ore si 30 de minute)).

Se considera ca programul unei zile incepe cu inceputul intervalului in care prima vaca care produce lapte si se inchiese cu sfarsitul intervalului in care ultima vaca da lapte. Nu se iau in calcul perioadele din afara programului (vad ca nici problema nu le ia in calcul in exemplu, altfel am avea 600 in loc de 300).

Am impratit cele doua cerinte in doua pentru a fi mai usor de inteles, dar dupa cum vezi poti rezolva fara probleme ambele cerinte cu aceasi structura repetitiva for (daca vrei mai multa eficienta)

Cred ca am vorbit destul, acum sa vedem algoritmul :

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("lapte.in");

ifstream g("lapte.out");

struct element_time_frame{

   int ora;

   bool tip;

   //Tip 0 -> Start interval

   //Tip 1 -> Stop interval

} v[10000];

int main(){

   int n, x;

   //Citire

   f >> n;

   for(int i=0;i<n;i++){

       //Start

       f >> x;

       v[2*i].ora = x;

       v[2*i].tip = 0;

       //Stop

       f >> x;

       v[2*i+1].ora = x;

       v[2*i+1].tip = 1;

   }

   n*=2;

   //Sortare (Buble Sort)

   bool ok = 1;

   while(ok){

       ok=0;

       for(int i=0;i<n-1;i++){

           if(v[i].ora>v[i+1].ora){

               swap(v[i],v[i+1]);

               ok=1;

           }

       }

   }

   //Cerinta 1

   int maxim = 0,start_curent = 0;

   int d = 0;

   for(int i=0;i<n;i++){

       //Verifica daca perioada e noua

       if(d==0) start_curent = v[i].ora;

       //Schimba numarul de intervale deschise

       if(v[i].tip == 0)d++;

       else d--;

       //Verifica daca perioada s-a terminat

       if(d==0){

           //Daca perioada curenta e mai mare decat maximul anterior

           if(v[i].ora - start_curent > maxim) maxim = v[i].ora - start_curent;

       }

   }

   g << maxim;

   //Cerinta 2

    maxim = 0;

    d = 0;

   for(int i=0;i<n;i++){

       //Schimba numarul de intervale deschise

       if(v[i].tip == 0)d++;

       else d--;

       //Faca perioada s-a terminat verifica timpul ramas pana la urmatoarea perioada

       if(d==0 && i<n-1){

           //Daca perioada curenta e mai mare decat maximul anterior

           if(v[i+1].ora - v[i].ora > maxim) maxim = v[i+1].ora - v[i].ora;

       }

   }

   g << " " << maxim;

}