x̄ - > Motorway problem -To minimize Sum of distances between cities

  

There are N cities (numbered from 0 to N-1) located along a road. The K-th city is situated A[K] from the beginning of the road in the west. Cities are numbered in ascending order of position, and no two of them lie in the same place. Formally, A[K] < A[K + 1] holds for every K from 0 to N-2.

The time needed to travel east from city X to the easternmost city equals A[N - 1] - A[X] unless there is a city Y to the east of X (as cars can drive only to the east) with a motorway to the easternmost city built. Then, travel time decreases to A[Y] - A[X] (time spent on the motorway is not considered). If city X has a motorway built, then the travel time from it equals 0.

There are no motorways right now, but one from any city to the easternmost city is planned to be built. Decide where to build it in order to minimize the sum of travel times from every city to the easternmost one. Write a function: def solution(A) that, given an array A of N integers, returns the minimum total travel time as described above.

As the result might be large, return its remainder when divided by 109 + 7.

Example 

Given A = [1, 5, 9, 12], the function should return 7.

• With the motorway from the 0th city the travel times would be: 0 for the 0th city as it has a motorway, 7 for the 1st city and 3 for the 2nd city: that is 10 in total.
• With the motorway from the 1st city the travel times would be: 4 for the 0th city, 0 for the 1st city and 3 for the 2nd city: that is 7 in total.
• With the motorway from the 2nd city the travel times would be: 8 for the 0th city, 4 for the 1st city and 0 for the 2nd city: that is 12 in total.

def solution(A):

    MOD = 10**9 + 7

    N = len(A)

    

    # Calculate the total travel time without building any motorways

    total_time = A[N-1] - A[0]

    

    # Initialize an array to store the minimum travel time for each city

    min_travel_time = [float('inf')] * N

    

    # Traverse the cities from left to right and find the minimum travel time to the easternmost city

    for i in range(N):

        for j in range(i + 1, N):

            min_travel_time[j] = min(min_travel_time[j], A[j] - A[i])

    

    # Initialize an array to store the maximum travel time for each city

    max_travel_time = [0] * N

    

    # Traverse the cities from right to left and find the maximum travel time to the easternmost city

    for i in range(N - 1, -1, -1):

        for j in range(i - 1, -1, -1):

            max_travel_time[j] = max(max_travel_time[j], A[i] - A[j])

    

    # Initialize the minimum total travel time

    min_total_time = total_time

    

    # Find the minimum total travel time with a motorway

    for i in range(1, N - 1):

        min_total_time = min(min_total_time, total_time - max_travel_time[i] + min_travel_time[i])

    

    return min_total_time % MOD

# Example usage:

A = [0, 1, 3, 6, 7, 9]

result = solution(A)

print(result)