Overview

This problem asks for the minimum total time to inspect \(N\) shelves lined up in a straight line exactly once, starting from a specified initial position. Since the total inspection time is constant regardless of the order of visitation, the key is to find a path that minimizes the total travel time.

Analysis

First, because we inspect every shelf exactly once, the total inspection time is always \(\sum_{i=1}^{N} T_i\) regardless of the order of visitation. Therefore, this problem reduces to “finding the minimum travel distance to visit all shelves starting from the initial position \(S\)”.

Since the shelves are lined up in a straight line, to visit all shelves, we must eventually traverse the entire interval from the leftmost shelf (shelf \(1\)) to the rightmost shelf (shelf \(N\)). If the starting position \(S\) is at either end (shelf \(1\) or shelf \(N\)), we only need to move in a straight line to the other end, resulting in a travel distance of \(N - 1\).

However, if the starting position \(S\) is not at either end, we must move in one direction first, then turn back and proceed to the other end. To minimize redundant back-and-forth movement, it is optimal to choose one of the following two patterns:

1. Going to the left end first, then to the right end: First, move from \(S\) to the left end (shelf \(1\)), then move from there to the right end (shelf \(N\)). Travel distance: \((S - 1) + (N - 1) = N + S - 2\)
2. Going to the right end first, then to the left end: First, move from \(S\) to the right end (shelf \(N\)), then move from there to the left end (shelf \(1\)). Travel distance: \((N - S) + (N - 1) = 2N - S - 1\)

By choosing the pattern with the smaller travel distance, we can minimize the travel time. A naive brute-force search (permutations) would take \(O(N!)\) time, which is far too slow to pass. However, by leveraging the linear nature of the movement, we can find the minimum travel distance in \(O(1)\) time.

Algorithm

1. Read the input and calculate the sum of the inspection times \(T_i\) as sum_T.
2. Calculate the travel distance when heading to the left end first: move1 = 2 * N - S - 1.
3. Calculate the travel distance when heading to the right end first: move2 = N + S - 2.
4. Find the minimum travel distance: min_move = min(move1, move2).
5. The final answer is the minimum travel distance multiplied by the adjacent travel time \(D\), plus the total inspection time sum_T.

Complexity

• Time Complexity: \(O(N)\) (It takes \(O(N)\) to read the input and calculate the sum of inspection times. Finding the path takes \(O(1)\).)
• Space Complexity: \(O(N)\) (To store the input as a list. If the input is read as a stream, it can be optimized to \(O(1)\).)

Implementation Points

• The constraint \(N \leq 10^6\) is quite large. In Python, using input() to read the standard input line by line can be slow and may lead to a TLE (Time Limit Exceeded).

• To speed up I/O, you can use sys.stdin.buffer.read().split() to read the entire input at once as a byte string and split it by whitespace.

• During the calculation, since \(N, D, S, T_i\) can be up to \(10^9\), the answer may exceed the range of a 32-bit integer. While Python handles integer overflow automatically, you must use 64-bit integers (such as long long in C++) when implementing in languages like C++.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    D = int(data[1])
    S = int(data[2])
    
    sum_T = sum(map(int, data[3:3+N]))
    
    move1 = 2 * N - S - 1
    move2 = N + S - 2
    
    min_move = move1 if move1 < move2 else move2
    
    ans = min_move * D + sum_T
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by or-glm5.2-high.