Ad
mofvs.xzrrooney

Apples

Algorithms
Logic

We have n piles of apples, and we want to move the piles into a single large pile using the least possible amount of energy. Only two piles can be combined at a time and two piles with a and b apples can be combined together with the cost of (a+b) energy units.

We want to know the minimum amount of energy required to combine all piles of apples together.

Input:
apple(n, lst)
where lst contains n numbers representing the number of apples in each pile.

Code
Diff
  • #include<algorithm>
using namespace std;
int apple(int n, int* a)
{
   if (n < 2) return 0;
   int* end = a+n;
   int sum = 0;
   while (end > a+1)
   {
      std::make_heap(a, end, greater<int>());
      std::pop_heap(a, end, greater<int>());
      --end;
      sum += (*a += *end);
   }
   return sum;
}
    • #include<stdio.h>
    • #include<queue>
    • #include<algorithm>
    • using namespace std;
    • int apple(int n,int* a)
    • int apple(int n, int* a)
    • {
    • priority_queue<int,vector<int>,greater<int> >q;
    • for(int i=0; i<n; i++)
    • q.push(a[i]);
    • int ans=0,tmp;
    • while(q.size()>=2)
    • {
    • tmp=0;
    • tmp+=q.top();
    • q.pop();
    • tmp+=q.top();
    • q.pop();
    • ans+=tmp;
    • q.push(tmp);
    • }
    • return ans;
    • if (n < 2) return 0;
    • int* end = a+n;
    • int sum = 0;
    • while (end > a+1)
    • {
    • std::make_heap(a, end, greater<int>());
    • std::pop_heap(a, end, greater<int>());
    • --end;
    • sum += (*a += *end);
    • }
    • return sum;
    • }