Hogyan oldható meg ez a mohó stratégiás feladat? (C++)
A feladat szövege:
Elakadtam a programozási feladatomban, melyet csatolva találhattok meg. Az első rész, az, hogy hány gép szükséges, sikerült. Viszont, a beosztás elkészítése, hogy melyik napon hányas gép végezze a munkát, az eddig nem, mégpedig az nem, hogy hogyan lehetne olyan naphoz, ahol korábbi gép még nem szerepel korábbi gépet beírni. Ebben szeretnék ötleteket kérni. A cout << G << endl; utáni rész ez.
Az eddigi kódom:
#include <iostream>
#include <cmath>
using namespace std;
const int MaxN = 10000;
const int MaxM = 100000;
struct munka
{
int s;
int n;
int g;
int h;
};
int main()
{
cerr << "Gepek" << endl;
/// deklaracio
int N;
int M;
double G;
int H[MaxM];
int m[MaxN] = {};
int t;
/// beolvasas
cerr << "N = ?: ";
cin >> N;
cerr << "M = ?: ";
cin >> M;
for (int i=0;i<M;i++)
{
cerr << i+1 << ". megrendeles hatarideje: ";
cin >> H;
}
/// Rendezes (hatarido szerint novekvoleg)
int s;
for (int i=0;i<M-1;i++)
{
for(int j=i+1;j<M;j++)
{
if (H > H[j])
{
s = H;
H = H[j];
H[j] = s;
}
}
}
/// Megoldas
for (int i=0;i<M;i++)
{
t = H;
m[t]++;
}
G = 0;
double msz = 0;
double gsz = 0;
for (int i=0;i<N;i++)
{
msz = msz + m;
gsz = ceil(msz / i);
if (gsz > G)
{
G = gsz;
}
}
cout << G << endl;
int nap = 0;
int gep = 1;
for (int i=0;i<M;i++)
{
if (nap < H[i])
{
nap++;
cout << nap << " " << gep << endl;
}
else
{
nap = 1;
gep++;
cout << nap << " " << gep << endl;
}
}
return 0;
}
feladat (1).pdf156,2 KB
Válasz
Téma törlésének kezdeményezése
C++MUNKA
HASONLÓ PROBLÉMÁK:
CRTP ősosztály miatt miért nem elég a _single_inheritance Visual C++-ban?
Szabadúszó szoftverfejlesztőt/programozót keresek!
Saját osztály, unique_ptr használata, .NET-hez hasonló a deklaráláshoz
Fájlból beolvasás láncolt listába C++
Feladat,rendezés nem kivitelezhető
C++ hatékonyabb megoldás
Else if c++
C++ Qt Creator automatikus mentés visszatöltése
Adatnyilvántartó program
Miért "egyesülnek" a szálak?
Beadandó. Meglévő C# kódból átírás Java koddá
C++ switch probléma
mutass többet!
hirdetés
Kezdd a változást velünk!
hirdetés
Az igazival bárhová elmennél…
hirdetés
Élethű játékélmény a Samsung Neo QLED TV-vel
válasza:Mi okoz problemat itt? Ha megvan a gepek szama, onnantol csak vegig kell menned egyesevel a munkakon, ha van szabad gep az aktualis napra, akkor azon a napon elvegezheto a munka, ha nincs, akkor lepsz a kovetkezo napra, ahol ismet rendelkezesedre all minden gep.
Miert hasznalsz double-t? Nem lehet fel munkat vegezni es fel gep sincs. Minek irsz kezzel ilyen hulladek rendezest, nem hasznalhatod a sort-ot az STL-bol? Igazabol rendezni sem szukseges.
válasza:Tudod, hogy van G geped osszesen, ezt kiszamoltad. Indulsz az elso naprol, mesz vegig a munkakon hatarido szerint novekvo sorrendben es adsz nekik egy gepet. Tehat az elso munkanak adsz egyet es marad G-1 geped, a masodik munkanak is adsz egyet es marad G-2 es igy tovabb. Ha G 0-ra csokken, az azt jelenti, hogy minden gepet kiosztottal, tehat ezen a napon nem tudsz tobb munkat elvegezni.
Lepsz a kovetkezo napra, ahol ismet van G geped. Ezt ismetelgeted addig, ameddig el nem fogynak a munkaid.
Köszönöm.
Rendben, megpróbálom.
válasza:"egy nap egy munka végezhető el"
Egy nap egy munka vegezheto el egy geppel. Tobb geppel tobb is.
Ha nem erted, akkor nezd meg a feladathoz mellekelt peldat.
Bemenet: 3 2 3 2 4 5 6 2
Ebbol pl. az elso napon csinalja a 2-es es a 8-as munkat is. Tehat ket munkat vegez el ugyanazon a napon (mivel 2 gep van).
De akkor menjunk vegig lepesenkent a peldan:
Az hataridok novekvo sorrendben: 2 2 2 3 3 4 5 6
Tudjuk, hogy van 2 gepunk osszesen.
1. NAP:
1. munka (2): 2 gepunk van, neki adjuk az 1-es gepet, marad 1
2. munka (2): 1 gepunk van, neki adjuk a 2-es gepet, marad 0
2. NAP:
1. munka (2): 2 gepunk van, neki adjuk az 1-es gepet, marad 1
2. munka (3): 1 gepunk van, neki adjuk a 2-es gepet, marad 0
3. NAP:
1. munka (3): 2 gepunk van, neki adjuk az 1-es gepet, marad 1
2. munka (4): 1 gepunk van, neki adjuk a 2-es gepet, marad 0
4. NAP:
1. munka (5): 2 gepunk van, neki adjuk az 1-es gepet, marad 1
2. munka (6): 1 gepunk van, neki adjuk a 2-es gepet, marad 0
Az eredeti sorrendre az eredmeny tehat "hatarido(nap, gep)" formaban:
3(2, 2) 2(1, 1) 3(3, 1) 2(1, 2) 4(3, 2) 5(4, 1) 6(4, 2) 2(2,1)
válasza:Sikerült ezzel a módszerrel megoldani. Viszont nem elég hatékony. Hogy lehetne ezen még hatékonyítani?
Jelenleg így néz ki a kód:
válasza:En kukaznam az egeszet, de ha mindenkeppen ezt akarod hegeszteni, akkor kezd azzal, hogy a rendezest lecsereled STL sort-ra, mert igy negyzetes komplexitassal rendezed a 100000 elemu tombodet (ketszer).
75. sortol is kuka, ott konkretan annyit kene implementalnod, amit a 13-as valaszban leirtam, a napokon pl. feleslegesen iteralsz.
Ha ezekkel megvagy, akkor elgondolkodhatsz rajta, hogy tulajdonkeppen miert nem kell egyaltalan rendezes, miert felesleges a munka struct, vagy miert hasznalsz double-t egesz szamokkal valo muveletekre.
Én szerintem konkrétan azt implementáltam le, amit a 13-as válaszban írtál: A napokon megyek végig, azon belül a rendezett határidőkön, majd a gépeken és így tovább.
Nem látom, hogy hogyan lehetne elhagyni a rendezést, hiszen a megoldásban erősen kihasználom -> így biztosítható, hogy korábbi határidejűnek ne adjunk határidőn túli napot.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!