infoarena

Aici puteti discuta despre problema Jsched (http://infoarena.ro/problema/jsched).

Salut ! Ma poate ajuta si pe mine cineva? am sortat crescator dupa x i-ar in caz de egalitate descrescator dupa y.
L.E. : Mi-a iesit pana la urma.

Nu cred ca e bine cum spui tu, adica cu sortatul in ordine crescatoare in functie de x.
Uite un contraexemplu:

2 2
3 1
6 2
7 100

Daca iei in ordine crescatoare obtii 1831. Se mai pot obtine si rezultate mai mici, precum: ..., 778, 766.
Mai degraba as inclina sa sortez descrescator dupa y.
L.E. Done! Nu era chiar asa, dar pe aproape cu acea sortare...

am sortat descrescator vectorul in functie de y iar in caz de egalitate crescator in functie de x
Functia care calculeaza este urmatoare:
....

for(int i=1;i<=n;i++)
   {
      int s=0;
      for(int j=1;j<=i;j++)
         s+=G[j].x;
   
      ans+=s*G.y;
      
   }

..
iau 0 pct si nu stiu dc :'(
Imi puteti da o sugestie?
Multumesc anticipat!!! :D

Greseala e in sortare. Sirul il sortezi in functie de ambele valori. Incearca sa gasesti o legatura intre x si y; cu cat contribuie fiecare pereche in realizarea costului final; si in functie de acea legatura sortezi

de 1h tot incerc faza cu sortarea si nu iese :'(
mai incerc maine:D
mersi oricum pt idee :)
noapte buna

pana la urma cum trebuie sa sortezi? ](*,)am sortat in mai multe feluri....  imi dau bine pe testul de la problema(chiar si  pe al tau) dar tot 0 iau :'(

[...]

De ce e corect sa sortezi asa ?

Este corect, dar dupa calculezi liniar rezultatu, nu cum a facut Lucian. Sper sa se prinda, daca nu ii explic eu :).

Va rog sa nu mai postati solutii directe. Poti sa dai hint-uri. "Trebuie sa faci X si Y si merge" nu ajuta pe nimeni la nimic.

 :'(  ](*,) problema asta ma omoara  ](*,).
Am calculat si liniar rezultatul dar tot degeaba :angry:
Sortarea pe care o fac e corecta (am verificat pe cateva exemple si imi da bine) :-k
Chiar nu stiu ce sa-i mai fac!!!! ](*,)

Tot nu e bine! Schimba idea !
uite un test pe care pica sursa ta :
7
2 10
1 8
5 3
1 1
9 8
4 3
6 10
Out(corect) : 443

eu nu stiu cum ti-a dat 443 ](*,)
care sunt costurile pt fiecare proces?

8
38
128
138
290
359
443
In locul tau as incerca sa gasesc alt mod de a a sorta elementele!

La aceasta problema nu e greu sa intuesti care e criteriul de sortare, dar totusi as vrea sa stiu daca este vre-o demonstrare matematica. Eu asa inteleg ca pentru a minimiza suma totala trebue sa minimizam suma la fiecare pas, iar suma la un pas curent v-a fi t[ i ]*p[ i ]+t[ i ]*suma(1..i-1) si deci trebue sa minimizam aceasta valoare, sau poate numai valoarea care depinde numai de variabilele curente adica t[ i ]*p[ i ] si daca e asa atunci este adevarat ca daca x/y este mai mare atunci x*y este mai mic ??  :?