Overview

This is a problem about delivering letters to locations aligned on a straight line. We need to find the minimum total fatigue required across all routes to deliver the letters.

Analysis

The key observation to solve this problem is to realize that “the fatigue cost to deliver a single letter to its destination is equal to the distance from the post office (Location 1) to the destination.”

For example, let us consider delivering a single letter addressed to Location \(3\). To start from Location 1, pass through Location 2, and deliver it to Location 3, the following two movements are involved: 1. Location 1 \(\to\) Location 2 (Since we have the letter in hand, \(1\) fatigue is incurred) 2. Location 2 \(\to\) Location 3 (Since we have the letter in hand, \(1\) fatigue is incurred)

Whether we deliver this letter in a single trip or split it across multiple trips, we must transport it along the path from Location 1 to Location 3. Therefore, a fatigue of exactly \(2\) is always incurred for this single letter.

This property applies to all letters. That is, each letter delivered to Location \(i\) (\(2 \leq i \leq N\)) incurs a fatigue of \((i - 1)\).

Therefore, no matter how we divide the letters into routes, the total fatigue across all routes remains invariant. It is simply the sum of \((i - 1)\) multiplied by the number of letters \(B_i\) addressed to Location \(i\). There is no room for optimization (such as minimizing or maximizing this value); we can find the answer simply by summing them up.

Algorithm

The array \(B\) represents the number of letters for each location from Location \(2\) to Location \(N\). In a 0-indexed array B, the element at index i corresponds to the number of letters \(B_{i+2}\) for Location i + 2. Since the distance to Location i + 2 is (i + 2) - 1 = i + 1, we can obtain the answer by adding (i + 1) * B[i] to the total fatigue ans.

Specifically, we perform the following calculation: $\( \text{Ans} = \sum_{i=2}^{N} (i - 1) \times B_i \)$

Complexity

• Time Complexity: \(O(N)\) Since we only need to traverse the elements of the array once and sum them up, the time complexity is \(O(N)\). This is fast enough to run well within the time limit even for \(N \leq 10^6\).
• Space Complexity: \(O(N)\) We need \(O(N)\) memory to store the input array B.

Implementation Notes

• Since the final result can be extremely large, you need to be careful of integer overflow. In Python, there is no limit on integer size, so you do not need to worry about this. However, in languages like C++, you must use a 64-bit integer type such as long long.

• Since the input size can be large, in Python, it is recommended to use sys.stdin.readline for fast I/O.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    B = list(map(int, input().split()))
    ans = 0
    for i, b in enumerate(B):
        ans += (i + 1) * b
    print(ans)

if __name__ == '__main__':
    main()

---

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