Here you have the link to the Problem Statement.
My Solution:
vector <int> find(vector <int> h) {
vector<pair<int, int> > a, v(h.size());
vector<int> ans;
int i, j;
for(i = 0; i < h.size(); ++i) {
v[i] = make_pair(h[i], i);
}
sort(v.begin(), v.end());
for(i = 0; i < v.size(); ++i) {
for(j = 0; j < a.size() && a[j].first == v[i].first; ++j);
if(j != a.size() && a[j].second > v[i].second) {
a.insert(a.begin() + j, v[i]);
}
else {
a.push_back(v[i]);
}
}
for(i = 0; i < a.size(); ++i) {
ans.push_back(a[i].second);
}
return ans;
}
My solution description:
I sort the tower by heights and then add the towers to the solution vector, in order, by height. The i-th tower is added at the beginning or at the end part of the solution vector, such that the vector is lexicographically the smallest(though, if there are equal values, I make sure that when they are inserted, they are in increasing order of indexes in the final solution vector).
My solution is based on the following two observations:
The minimum distance between the first and the last tower is equal to the sum of all heights minus the minimum distance.
To obtain an arrangement of the towers that has the minimum distance between the first and the last towers we can go through the tower heights either from the maximum to the minimum element and add the current height to one of the extremities of the free space in the final vector, either from the minimum to the maximum and add the current height to the border of the existing vector.
My problem is that I can't prove these two(1. and 2.) statements. Will you please help me?