✂️ 初学者友好指南 ‘Divide an Array Into Subarrays With Minimum Cost I’ - 问题 3010 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：

• 长度为 n 的整数数组 nums。
• 子数组的 成本 定义为其第一个元素的值。

目标：

• 将数组恰好划分为三个连续子数组。
• 最小化总成本，即三个子数组首元素之和。

直觉

由于子数组必须是连续的，原数组的第一个元素 nums[0] 必然是第一个子数组的首元素，因而必然计入总成本。

要使和最小，需要从剩余元素 (nums[1:]) 中再选出两个作为第二、第三子数组的起始点。最优的选择就是该后缀中的两个最小值，因为它们将成为第二、第三子数组的首元素。

示例讲解

示例 1

nums = [1, 2, 3, 12]

• 第一个元素：1
• 剩余元素：[2, 3, 12]
• 两个最小值：2 和 3
• 最小总成本：1 + 2 + 3 = 6

示例 2

nums = [10, 3, 1, 1]

• 第一个元素：10
• 剩余元素：[3, 1, 1]
• 两个最小值：1 和 1
• 最小总成本：10 + 1 + 1 = 12

代码块

C++

class Solution {
public:
    int minimumCost(vector& nums) {
        // The maximum possible value based on constraints
        int min1 = 51;
        int min2 = 51;

        // Start from index 1 because nums[0] is always included
        for (int i = 1; i  // (loop logic omitted in original)
    }
};

Python

# nums[0] is always the start of the first subarray
first_val = nums[0]

# Get the rest of the array and sort to find the two smallest elements
remaining = nums[1:]
remaining.sort()

# Sum the first element and the two smallest from the rest
return first_val + remaining[0] + remaining[1]

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const firstVal = nums[0];

    // Extract everything after the first element
    let remaining = nums.slice(1);

    // Sort numerically in ascending order
    remaining.sort((a, b) => a - b);

    // The result is the sum of the first element and the two smallest remaining
    return firstVal + remaining[0] + remaining[1];
};

关键要点

• 固定约束： 认识到 nums[0] 必然计入成本后，问题就转化为再选两个元素。
• 贪心选择： 从剩余数组中挑选两个最小值即可保证最小的可能和。
• 效率： 若在一次遍历中找到两个最小值，时间复杂度为 O(n)；若排序，则为 O(n log n)。在本题约束下，两种方法都足够快。

最后思考

该问题展示了看似复杂的划分任务，在明确成本定义后可以变得非常简单。通过观察只有每个子数组的首元素会影响成本，我们把问题转化为一次贪心选择——这种思路在实际优化场景（例如降低负载均衡器的入口延迟）中经常出现。