Cod sursa(job #1707939)

Utilizator gincota.nicolaiGincota Nicolae gincota.nicolai Data 26 mai 2016 10:14:34
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
 
struct piatra{
	int val,greu,ind;
};
piatra A[100100];
int N,M;
double Gr,rs;

bool comp(piatra a,piatra b){
	return 1.0*a.val/a.greu > 1.0*b.val/b.greu;
}
/*void Qsort(int y, int z)
{
	int x=1.0*A[y+(z-y)/2].val/A[y+(z-y)/2].greu;
	int i=y; int j=z;
	while(i<=j)
	{
		while(1.0*A[i].val/A[i].greu <x) i++;
		while(1.0*A[j].val/A[j].greu >x) j--;
		if(i<=j)
		{
			swap(A[i].val,A[j].val);
			swap(A[i].greu,A[j].greu);
			swap(A[i].ind,A[j].ind);
			i++;
			j--;
		}
	}
	if(i<z) Qsort(i,z);
	if(y<j) Qsort(y,j);
}*/
void greedy()
{	int i;
    for (i=0,Gr=M;i<N && Gr;++i){
    	fo <<"Diamtul " << A[i].ind << ' ';
		if(Gr >= A[i].greu){
			Gr-=A[i].greu;
			rs+=A[i].val;
			fo<<" cu valoarea "<<A[i].val<<" lei\t";
			fo<< A[i].greu<<" grame\t";
			fo << 100 << "%\n";	
		} 
    	else{
    		rs+=1.0*Gr*(1.0*A[i].val/A[i].greu);
    		fo<<" cu valoarea "<<A[i].val*Gr/A[i].greu<<" lei\t";
    		fo<<Gr<<" grame\t";
			fo << (100.0*Gr/A[i].greu)<<"%";
			Gr = 0;	
		}
	
	}
}
 
 
int main()
{
    int i;
    fi>>N>>M;
    for (i=0;i<N;++i)
    {
        fi>> A[i].greu>>A[i].val;
        A[i].ind = i+1;
    }

    sort(A,A+N,comp);
    greedy();
	fo << "\nPretul total este " << rs<<" lei";
    return 0;
}