Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1226 Planificare  (Citit de 2134 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Ianuarie 22, 2012, 14:26:21 »

Aici puteți discuta despre problema Planificare.
« Ultima modificare: Ianuarie 22, 2012, 20:33:52 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #1 : Ianuarie 23, 2012, 17:36:41 »

Am folosit un multiset si cautare binara dar iau doar 40p cu TLE. Cred ca e de la metoda advance pe care o folosesc in cautarea binara. Pentru pozitia m, avansez iteratorul cu m pozitii. Fac ceva de genul

Cod:
it = T.begin();
advance(it, m);
int x = *it;

Pot sa fac ceva sa pastrez ideea asta si sa iau 100p ? Sau trebuie neaparat folosit lower_bound ?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #2 : Ianuarie 23, 2012, 17:58:13 »

Pai analizeaza-ti putin complexitatea. Nu are niciun sens sa faci cautare binara pe o structura care nu iti permite acces indexat. Daca tie sa accesezi pozitia p iti trebuie O(p) timp n-ai rezolvat nimic. E mai rau decat daca faceai cautarea bruta, liniara. Fie folosesti lower_bound, fie iti faci arborele tau de cautare, dar iti dai seama ca nu prea merita. Ai sa gasesti alte probleme unde trebuie sa-l scrii de la 0 fiindca nu te ajuta set-ul.
Memorat
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #3 : Ianuarie 27, 2012, 10:14:39 »

As avea nevoie de putin ajutor la codul acesta :

Cod:
fin >> n >> k;
for(int i = 1; i <= n; i ++)
fin >> t[i].start >> t[i].final;

int ct = 1;
int pred = 0;
sort(t + 1, t + n + 1, cmp());
spectacol.insert(t[1].final);

Primesc segmentation fault la linia cu
Cod:
spectacol.insert(t[1].final)
Are cineva vreo idee de ce se intampla asta?
T e o structura cu final de tip int ... si multisetul e declarat multiset<int> spectacol;
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #4 : Ianuarie 27, 2012, 16:54:15 »

Din cod nu pot trage nicio concluzie... pune toata sursa
Memorat
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #5 : Ianuarie 27, 2012, 18:37:27 »

Cod:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

const char iname[] = "planificare.in";
const char oname[] = "planificare.out";
multiset <int> spectacol;
multiset <int>::iterator it;

ifstream fin(iname);
ofstream fout(oname);

int n , k;

struct timp
{
int final, start;
};

timp t[100002];
int ap[100002];


struct cmp
{
bool operator()(const timp &i, const timp &j)const
{
if(i.final > j.final)
return 0;
else
if(i.final == j.final)
if(i.start > j.start)
return 0;
return 1;
}
};


int main()
{
fin >> n >> k;
for(int i = 1; i <= n; i ++)
fin >> t[i].start >> t[i].final;

int ct = 1;
int pred = 0;
sort(t + 1, t + n + 1, cmp());
spectacol.insert(t[1].final);
int i = 0, ocupate = 1;
for(i = 2; i <= n; i ++)
{
it = spectacol.lower_bound(t[i].start);
if(it != spectacol.begin() && *it > t[i].start)
--it;
if(*it < 0)
it = spectacol.begin();
if(*it <= t[i].start && *it > 0)
{
spectacol.insert(t[i].final);
spectacol.erase(it);
++ct;
}
else
if(ocupate < k)
{
ocupate ++;
spectacol.insert(t[i].final);
++ct;
}

}


fout << ct << "\n";
return 0;
}
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #6 : Ianuarie 27, 2012, 19:02:35 »

Pe exemplu mie imi merge (gcc 4.2).
Am pus return 0 dupa primul insert in multiset si iti da incorect pe infoarena,altfel segfault.
Deci probabil in for-ul principal ai un bug.
Memorat
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #7 : Ianuarie 30, 2012, 11:37:21 »

Am descoperit ca problema era de la
Cod:
spectacol.erase(it);
. Acolo vreau sa sterg emisiunea la care o leg pe cea curenta (ca sa nu imi mai ramana in multiset si sa nu pot lega alte emisiuni de aceeasi emisiune). De la instructiunea aceea primesc KBS 6 SIGABRT. Se poate modifica valoarea de la adresa it intr-una cat mai mare ca sa evit problema fara sa folosesc functia erase()?   d'oh!
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #8 : Ianuarie 30, 2012, 11:45:22 »

Incearca sa apelezi intai functia erase si apoi functia insert.
Memorat

Am zis Mr. Green
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #9 : Ianuarie 30, 2012, 13:13:27 »

Incearca sa apelezi intai functia erase si apoi functia insert.

Cod:

if(*it <= t[i].start && *it > 0)        
{          
     spectacol.erase(it);          
     spectacol.insert(t[i].final);            
     ++ct;      
}


Am incercat acum, la fel KBS SIGABRT 6.

L.E : SOLVED - am rescris tot codul  Smile
« Ultima modificare: Ianuarie 30, 2012, 13:40:41 de către Vlad Eugen Dornescu » Memorat
NicuCJ
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #10 : Septembrie 02, 2012, 16:15:28 »

Am facut asa:
Am bagat intr-un heap (sa-i zicem heap1) toate canalele.
Am sortat emisiunile crescator dupa timpul de incepere.
Pe rand, am bagat intr-un heap (sa-i zicem heap2) timpul de final al emisiunii curente si primul canal liber ( heap1.top() ), scotand din heap1 canalul, atat timp cat heap1 nu era gol.
La fiecare pas, scoteam din heap2 emisiunile terminate, introducand in heap1 canalele eliberate astfel.
Daca heap1 era gol, inseamna ca emisiunea curenta nu avea niciun canal disponibil deci nu se rula.

Nu inteleg de ce iau 0 pe ea (toate-s incorecte). Poate m-ati putea ajuta cu un test care sa-mi "explice" de ce solutia mea nu e buna :-"
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines