Input is a vector of positive integers. You are to shrink it progressively. Each step you remove 2 selected elements, and replace with their sum. Therefore vector size drops by 1 at each step, until there’s one element left.

At each step there’s a cost, which is defined as that sum.

Eg: {4,2,1} becomes {4,3} after you combine 2/1. The cost at this step is the sum 2+1=3.

Q1: For a given vector, find a sequence of steps with the lowest total cost. Test your code in c++
Q2: how would you optimize your code, assuming high data volume.

```#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional> // std::greater
using namespace std;

vector<int> vec = { 3,2,1 }; // a std::set will fail when duplicate values show up like {3,3}
priority_queue<int, vector<int>, std::greater<int> > pq(vec.begin(), vec.end());

void dumpVector(string msg) {
cout << msg << ", size = " << vec.size() << endl;
for (auto it = vec.begin(); it != vec.end(); ++it) cout << *it << ' ';
cout << endl;
}

int operateVector(int sum = 0) {
auto lowestItem = min_element(vec.begin(), vec.end());
sum += *lowestItem;
vec.erase(lowestItem); // now s1 is an invalidated iterator and unusable

//remove() is bad as it removes all not one item having target value!
//v.erase(std::remove(v.begin(), v.end(), *lowestItem), v.end());

dumpVector("afer erase");
return sum;
}

void dumpHeap(string msg) {
auto clone = pq;
cout << msg << ", size = " << clone.size() << endl;
for (; !clone.empty();clone.pop()) {
std::cout << clone.top() << ' ';
}
cout << endl;
}
int operateHeap(int sum = 0) {
sum += pq.top();
pq.pop();
//dumpHeap("afer pop");
return sum;
}

int f1(int sum = 0) {
return operateHeap(sum);
}
int main87() {
int totalCost = 0;
for (; pq.size()>1;) {
int sum = f1(f1()); //call f1() twice recursively.
pq.push(sum);
dumpHeap("afer push");
totalCost += sum;
}
cout << "total cost = " << totalCost << endl;
return 0;
}
```