The other question in this batch is LC 53. Maximum Subarray :) Your office is relocating to the top floor of a building with n+1 floors, indexed from 0 to n. Currently, boxes of equipment and supplies are scattered across the lower floors (0 to n-1), and you need to transport all of them to the top floor (n). Rules: You start at the top floor (n). You can take the elevator down to any floor i and then return to the top (n). It takes (n - i) minutes to travel down to floor i and the same time to return. At each stop, you can load a maximum of one box from that floor into the elevator. Loading and unloading a box together take 1 minute. Input: An integer n (1 ≤ n ≤ 10⁵) — the top floor index. An array of n integers, where boxes[i] (0 ≤ boxes[i] ≤ 10⁹) represents the number of boxes on floor i. Output: A single long integer — the minimum time required to move all boxes to the top floor.

解法

每次去 i 层往返耗时 2*(n-i) + 1。为了把 i 层 boxes[i] 个箱子全部搬走需要 boxes[i] 次往返，所以单层贡献 boxes[i] * (2*(n-i) + 1)。直接求和即可。时间复杂度 O(n)，空间复杂度 O(1)。

from typing import List

def getMinimumTime(n: int, boxes: List[int]) -> int:
    total = 0
    for i in range(n):
        total += boxes[i] * (2 * (n - i) + 1)
    return total

class Solution {
    long getMinimumTime(int n, int[] boxes) {
        long total = 0;
        for (int i = 0; i < n; i++) {
            total += (long) boxes[i] * (2L * (n - i) + 1);
        }
        return total;
    }
}

class Solution {
public:
    long long getMinimumTime(int n, vector<int>& boxes) {
        long long total = 0;
        for (int i = 0; i < n; i++) {
            total += (long long) boxes[i] * (2LL * (n - i) + 1);
        }
        return total;
    }
};