Pagini recente » Cod sursa (job #1910930) | tudor | Cod sursa (job #1151240) | Cod sursa (job #676816) | Cod sursa (job #435061)
Cod sursa(job #435061)
#include <iostream>
using namespace std;
struct Gutuie
{
int inaltime;
int greutate;
bool ales;
};
bool myCompare( Gutuie g1, Gutuie g2 )
{
if (g1.greutate == g2.greutate)
return g1.inaltime > g2.inaltime;
return g1.greutate > g2.greutate;
};
int main()
{
//cout << "Hello world!" << endl;
/*
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
sort(A, A + N);
for(int i = 0 ; i < N; i++)
cout << A[i] << " ";
*/
int n,h,u;
FILE *fin = fopen("gutui.in","r");
FILE *fout = fopen("gutui.out","w");
Gutuie* g;
fscanf(fin,"%d %d %d",&n,&h,&u);
g = (Gutuie *)malloc(sizeof(Gutuie) *n);
for (int i = 0 ; i < n ; i++)
{
fscanf(fin,"%d %d",&g[i].inaltime,&g[i].greutate);
g[i].ales = false;
}
sort(g, g + n, myCompare);
for (int i = 0 ; i < n ; i++)
cout << g[i].inaltime << ' ' << g[i].greutate << '\n';
cout << '\n';
int total = 0;
int u_curent = 0;
int prim = 0;
int rezervat = 0;
int maxh = 0;
int k = 0;
bool continua = true;
bool alestot = false;
while (continua)
{
continua = false;
alestot = true;
rezervat = 0;
maxh = 0;
for (int i = 0 ; i < n ; i++)
{
if(g[i].ales || g[i].inaltime + u_curent > h)
{
//gutuia a depasit inaltimea maxima
//nu mai poate fi culeasa
//sau a fost deja aleasa
//g[i].ales = true;
continue;
}
//if(!g[i].ales && alestot)
if(!g[i].ales)
{
//salvam indexul primei gutui care poate fi culeasa
//in caz ca toate gutuile pot fi culese
//TODO: in acest caz trebuie culeasa cea mai inalta gutuie?
if(g[i].inaltime > maxh)
{
prim = i;
maxh = g[i].inaltime;
}
if(alestot) //prima gutuie care se poate culege
{
rezervat = (h - (g[i].inaltime + u_curent))/u - 1;
k = i;
//rezervat gutui se pot culege pana se culege aceasta gutuie
alestot = false;
continue;
}
//continue;
}
//if(!g[i].ales && (g[i].inaltime + u_curent + u > h || g[i].inaltime + u_curent + rezervat > h))
if(g[k].inaltime <= g[i].inaltime && (g[i].inaltime + u_curent + u > h || rezervat <= 0))
{
//gutuia nu poate fi aleasa la urmatoarea iteratie dupa culegere gutuilor rezervate
g[i].ales = true;
total += g[i].greutate;
u_curent += u;
continua = true;
cout << g[i].greutate << ' ' << g[i].inaltime << '\n';
break;
}
else
rezervat--;
/*if(g[i].inaltime + u_curent < h)
{
//gutuia poate fi culeasa
//cate gutui pot culege pana sa culeg aceasta gutuie?
k = (h - g[i].inaltime)/u;
//adica k * u cm
k *= u;
rezervat += k;
//if(!k) //daca poate fi culeasa la urmatoarea iteratie
// continue;
}*/
}
if(!continua && !alestot)
{
//daca toate gutuile se pot culege ulterior
g[prim].ales = true;
total += g[prim].greutate;
u_curent += u;
cout << g[prim].greutate << ' ' << g[prim].inaltime << '\n';
continua = true;
}
}
fprintf(fout,"%d",total);
fclose(fin);
fclose(fout);
return 0;
}