Some thoughts on this problem:

• sorting the cities according to population, then traversing the cities in increasing order of population is useful. It guarantees that at city_i, all previous cities (cities from 0 to i-1) have less population and hence the cost should be increased by city_i's population * sum of distances from city_i to all previous cities

• We can do simple mathematics to get sum of distances from city_i to all previous cities efficiently. Assume that cities from 0 to i-1 are divided into to categories:

  1. left cities (cities to the left of city_i, i.e. having coordinate < city_i's coordinate), assume there're l left cities which are city_l1, city_l2, ... sum of distances from city_i to these cities would be (city_i's coordinate - city_l1's coordinate) + (city_i's coordinate - city_l2's coordinate) + ... As we see, city_i's coordinate term is added l times (l = left cities count) and all left cities coordinates are subtracted, So the expression can be simplified as: left cities distances sum = city_i's coordinate * left cities count - left cities coordinates sum
  2. right cities (cities to the right of city_i, i.e. having coordinate > city_i's coordinate), assume there're r right cities which are city_r1, city_r2, ... sum of distances from city_i to these cities would be (city_i's coordinate - city_r1's coordinate) + (city_i's coordinate - city_r2's coordinate) + ... As we see, city_i's coordinate term is subtracted r times (r = right cities count) and all right cities coordinates are added, So the expression can be simplified as: right cities distances sum = right cities coordinates sum - city_i's coordinate * right cities count

• To get right & left cities count & coordinate sum, we can use augmented BST to store visited cities coordinates, we can insert, get count of values > threshold, get sum of values > threshold, get count of values < threshold, get sum of values < threshold, all in O(log n) time complixity, hence the overall time complixity is O(n log n)