Advertisement
Guest User

Untitled

a guest
Oct 15th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n,Gmax;
  6. struct obiect
  7. {
  8. int g,v;
  9. };
  10. obiect a[10001];
  11.  
  12.  
  13. void Citire()
  14. {
  15. int i;
  16. cin>>n>>Gmax;
  17. for(i=1;i<=n;i++) cin>>a[i].g>>a[i].v;
  18. }
  19.  
  20.  
  21. bool comp(obiect A,obiect B)
  22. {
  23. return(A.v*B.g>A.g*B.v);
  24. }
  25.  
  26. void Greedy()
  27. {
  28. int i;
  29. double CostMax=0;
  30. sort(a+1,a+n+1,comp);
  31. for(i=1;i<=n and Gmax>=a[i].g;i++)
  32. {
  33. Gmax-=a[i].g;
  34. CostMax+=a[i].v;
  35. }
  36. if(i<=n and Gmax>0)
  37.  
  38. CostMax+=(double)(Gmax*a[i].v)/a[i].g;
  39. cout<<CostMax<<endl;
  40. }
  41.  
  42. int main()
  43. {
  44. Citire();
  45. Greedy();
  46. return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement