Placute

[•alex_unix]

@ Mihai22e
Eu am o abordare greedy, folosit o coada, initial goala.
Am sortat mai intai porcii dupa greutate. Am pornit de la ultimul porc (cel cu greutatea cea mai mare) pana la cel cu greutatea cea mai mica. Cand nu puteam sa iau un porc din sir, treceam "peste" el si il puneam in coada. Aici iti dai seama, cum sirul este sortat, restu porcilor ramasi in sir au greutatile mai mici decat ale celor din coada. Deci, la fiecare pas, incerc sa iau un porc mai intai din coada. Daca nu aveam nici un porc disponibil in coada, luam urmatorul din sir, pana cand nu mai pot sa iau nici un porc.
Am facut eu un exemplu, pentru ca pe cel de la problema nu se vede greedy-ul.

Cod:

6 3
6 2
5 2
4 3
1 2
2 2
3 1

Deci sunt 6 porci pe care ii sortezi.
Sortare :

Cod:

6,2  5,2  4,3  3,2  2,2  1,1

Il iau pe primu : 6,2
Nu am nimic in coada, deci incerc sa il iau pe 5,2 . Nu pot sa il iau, deci il bag in coada. il iau pe 4,3 .
Urmatorul pas, ma uit in coada si il scot pe 5,2 .
Urmatorul pas, incerc sa ii iau pe 3,2 si pe 2,2 dar nu pot. Il iau pe 1,1. Acum am terminat elementele din sir, dar mai am coada. E evident ca in coada nu pot sa fie decat porci cu aceeasi culoare, deci pur si simplu il scot pe primu din coada, daca exista vreunu.
Deci il scot pe 3,2 din coada si am terminat.
Solutia optima 6 + 4 + 5 + 1 + 3 = 19.

Sper ca am reusit sa iti dau o idee . Nu prea sunt asa bun la explicatii.
P.S. Trebuia folosit long long
http://infoarena.ro/job_detail/842995

[•veleandu]

Eu am sortat ( NlogN ) si apoi ...

am scos O( N ).

Ideea e sa te plimbi cu "2" pointeri in felul urmator.
Daca ai sirul sortat dupa greutatea porcilor descrescator ..
Si sa zicem ca primi 5 porci sunt de culoare 1 ..
O sa fie ceva de genul.
10 1
9 1
8 1
7 1
6 1

Si tu parcurgi cu 1 pointer "varful" stivei .. si vezi ca ai porcul cu greutate 10. - "il scoti"
Apoi mergi in continuare cu al 2-lea pointer si scoti un porc care nu are culoarea '1'.

Apoi cu primul pointer, care arata cel mai mare porc, il scoti ..
Apoi cu pointerul 2 iterezi in continuare.

Acum. ( 1 )
De ce merge?
Daca primi x porci sunt de culoarea 1 .. e clar ca o sa fie scosi in oridnea asta .. porcul 1 .. primul porc care are culoarea != cu 1 .. porcul 2 ... porcul x ..

Acum, dupa ce am terminat un 'sir' ( adica o secventa in care aveam porc de culoare 1 .. altceva .. porc de culoare 1 .. altceva. )
! aici trebuie adaugat faptul ca daca am culorile 1 1 1 2 1 1 1 .. tot un sir am, deoarece toti cei 6 * 1 vor fi scosi conform regulei. adica .. 1 .. altceva ..1 .. altceva .. 1 .. etc. ^^

Acum, dupa ce am terminat sirul, sa zicem ca culoarea mea e '2' ... si SUNT SIGUR ca e cel mai 'valoros' porc.
Unde il gasesc pe urmatorul diferit de 2?

hmm .. Surprinzator, problema are o legatura cu cea cu parantezarile corecte ^^
De ce?
Deoarece se poate reformula aceasta 'subproblema' in felul urmator.

sa zicem ca culoarea celui mai valoros porc este 1 )

Putem reprezenta sirul de culori ca fiind '1' daca culoarea este 1 .. si 0 altfel..

Sa avem exemplu.

1100111001000011111
Si putem spune ca o sa se termine "domnia" sirului ( cum am spus mai sus .. ) 1 altceva ..1 .. altceva .. 1 .. altceva ..
pe pozitia x, astfel incat .. numarul de 1 si de 0 este egal pana la pozitia x, si pozitia x+1 este 0.

Adica .. daca am avea -1 in loc de 0 ..
Ar fi cea mai mare pozitie a.i. suma pana acolo este pozitiva.
Sau cea mai lunga parantezare corecta care incepe de la "inceput" ( de unde incepe sirul ).

xD
Poate ca nu am fost foarte coerent, dar in principiu cam asta ar fi ideea.

Daca suntem la pozitia x, si gasim acea pozitie cheie descrisa mai sus la pasul y .. atunci putem sa punem toti porcii intre x si y, si sa consideram y ca fiind inceputul algoritmului.
Nu putem gasi pozitia 'y' atunci cand numarul de 1 este mai mare decat cel de 0 pe tot parculsul sirului .. Ex: 1101010111

Atunci numaram cati de '0' sunt .. si luam toti porcii marcati cu '0' si acel numar+1 de porci marcati cu '1' ..

Aparent pare destul de greu de implementat .. poate daca se reformuleaza altfel, o sa fie mai ok ..

Dar asa mi s-a parut cel mai usor de explicat.

Craciun Fericit, si Sarbatori Fericite, Infoarena!

[•deneo]

@Alex Velea
Am facut la fel ca tine dar luam incorect
Am renuntat si am bagat heap

[•veleandu]

mie mi-a mers ^^

Si in principiu ideea e buna ..
Ai prima culoare x.

Gasesti ultima pozitie pentru care numarul de porci cu 'x' este egal numarul de porci de alte culori .. si nu ai ajuns sa ai mai multi porci de alte colori pe parcurs.

Daca dupa ce ai facut asta ai ajuns sa ai mai multi porci de culoare x pana la final .. iei numaru_de_porci_de_alte culori pe toti .. si iei primi porci de culoare x + 1 ^^

Cod:

    for ( ; ok; ){
        // mergem cu ind1
        for ( ; ( Pig[ind1].color == last_color || Viz[ind1] == 1 ) && ind1<=n ; ind1++ )
            ;
        if ( ind1 <= n ){
            rez += Pig[ind1].cost;
            Viz [ind1]=1;
            last_color = Pig[ind1].color;
            swap ( ind1, ind2 );            
        }
        else {
            ok=0;
        }
    }

Sper sa te ajute =))

[•deneo]

fuck, am uitat sa pun un viz )
ms veli ^_^

[•geniucos]

Puteti sa imi dati si mie niste teste?Imi merg primele 4 si apoi am TLE si WA dar sunt sigur ca TLE-le sunt de la o greseala in program si imi cicleaza.
Multumesc anticipat!