Overview

When delivering letters to locations aligned on a straight line, the minimum total fatigue incurred to deliver the letters to their destinations can be found with a very simple formula. This is because each letter consumes fatigue in proportion to the distance from the post office to its destination.

Analysis

In this problem, it may seem important to consider when and by which route to deliver the letters, but in fact, the total fatigue does not depend on the delivery method.

To deliver a single letter addressed to location \(i\), it must inevitably be transported from location 1 to location \(i\). Since the fatigue incurred during movement is equal to the “number of letters currently carried,” this single letter will generate exactly 1 unit of fatigue in each interval it traverses (\(1 \to 2\), \(2 \to 3\), \(\ldots\), \(i-1 \to i\)). In other words, the total fatigue generated by a single letter addressed to location \(i\) is exactly \(i-1\).

Whether you deliver the letters in multiple trips or carry them together with letters for other destinations, the fact remains that each letter addressed to location \(i\) must traverse each interval from location 1 to location \(i\). Therefore, the \(B_i\) letters addressed to location \(i\) will always generate a total fatigue of \((i-1) \times B_i\).

Thus, the total fatigue to deliver all letters can be found simply by calculating \((i-1) \times B_i\) for each location and summing them up.

Algorithm

You are given the number of locations \(N\) and the number of letters \(B_i\) to be delivered to each location \(i\) (\(2 \leq i \leq N\)).

1. Initialize a variable to store the answer (such as a long long type) to 0.
2. Loop \(i\) from 2 to \(N\), and add \((i - 1) \times B_i\) to the answer.
3. Print the calculated total sum.

This algorithm is just a single loop, has a very low computational complexity, and runs extremely fast.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\) (If storing the input in an array. It can be reduced to \(O(1)\) if you process the input on the fly)

Implementation Points

• Since \(N\) can be up to \(10^6\) and \(B_i\) up to \(10^7\), the final answer may exceed the range of a 32-bit integer (such as int). Make sure to use a 64-bit integer type (such as long long in C++) for the variable storing the answer and during the calculation.

• In C++, using fast I/O (ios_base::sync_with_stdio(false); cin.tie(NULL);) is helpful to process the input of size \(N \le 10^6\) quickly. Additionally, by calculating the sum on the fly instead of storing the inputs in an array, you can reduce the space complexity to \(O(1)\).

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> B(N + 1, 0);
    for (int i = 2; i <= N; ++i) {
        cin >> B[i];
    }
    
    long long ans = 0;
    for (int i = 2; i <= N; ++i) {
        ans += (long long)(i - 1) * B[i];
    }
    
    cout << ans << "\n";
    
    return 0;
}

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