software

🛂 初学者友好指南 “Divide an Array Into Subarrays With Minimum Cost II” - Problem 3013 (C++, Python, JavaScript)

发布: (2026年2月2日 GMT+8 09:28)
9 min read
原文: Dev.to

I’m ready to translate the article for you, but I need the text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the article text, I’ll translate it into Simplified Chinese while preserving the original formatting, markdown, and technical terms.

Problem Overview

将数据划分为最佳片段是计算机科学中的经典挑战，通常需要在特定约束和效率之间取得平衡。
本题要求我们在确保划分点彼此之间的 距离 符合要求的前提下，找到划分数组的最低成本。这是一个将滑动窗口技术与高级数据结构相结合，以维护移动数据的有序视图的绝佳练习。

你将得到

  • 一个整数数组 nums。
  • 一个整数 k，表示必须创建的子数组数量。
  • 一个整数 dist，限制第二个子数组和最后一个子数组的起始索引之间的最大距离。

目标

最小化总成本，其中子数组的成本是其 第一个元素。
由于第一个子数组总是从索引 0 开始，nums[0] 必然计入成本。
我们需要从数组其余位置中再选取 k‑1 个起始索引，使得总和最小并满足 dist 约束。

形式化

设 k 个子数组的起始索引为

[ p_1, p_2, \dots, p_k ]

  • p_1 始终为 0。
  • 必须从范围 1 … n‑1 中选择 k‑1 个索引。
  • 约束

[ p_k - p_2 \le \text{dist} ]

意味着所有选中的索引（从第二个到第 k 个）必须位于大小为 dist 的窗口内。

当我们将大小为 dist 的窗口在数组上滑动时，需要快速求出该窗口内 k‑1 个最小元素 的和。
为此，我们使用 树状数组（Fenwick Tree） 并结合 坐标压缩。这使我们能够对数字进行“排名”，并利用二进制提升在对数时间内找到最小值。

示例

nums = [1,3,2,6,4,2], k = 3, dist = 3

我们必须从窗口中挑选 k‑1 = 2 个索引。

  • 窗口大小为 dist + 1 = 4。

  • 如果第一个选中的索引是 1，则最后一个索引最多可以是 1 + dist = 4。

    查看索引 1 … 4：[3, 2, 6, 4]。
    其中最小的两个是 2 和 3。
    成本 = nums[0] + 2 + 3 = 1 + 5 = 6。

  • 如果第一个选中的索引是 2，则最后一个索引可以到 5。

    查看索引 2 … 5：[2, 6, 4, 2]。
    其中最小的两个是 2 和 2。
    成本 = 1 + 2 + 2 = 5。

可能的最小成本是 5。

参考实现

C++（GNU C++17）

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int max_rank;
    vector<int> bit_count;
    vector<long long> bit_sum;
    vector<int> sorted_values;

    // Add / remove a value from the BIT
    void update(int idx, int count_delta, long long val_delta) {
        for (; idx <= max_rank; idx += idx & -idx) {
            bit_count[idx] += count_delta;
            bit_sum[idx]   += val_delta;
        }
    }

    // Query sum of smallest `target` elements
    long long query(int target) {
        int idx = 0;
        int cur_k = 0;
        long long cur_s = 0;
        for (int i = 1 << (31 - __builtin_clz(max_rank)); i; i >>= 1) {
            int next_idx = idx + i;
            if (next_idx <= max_rank && cur_k + bit_count[next_idx] < target) {
                idx   = next_idx;
                cur_k += bit_count[next_idx];
                cur_s += bit_sum[next_idx];
            }
        }
        // add the remaining part of the (target‑cur_k)‑th element
        return cur_s + 1LL * (target - cur_k) * sorted_values[idx];
    }

public:
    int minCost(vector<int>& nums, int k, int dist) {
        int n = nums.size();

        // coordinate compression
        sorted_values = nums;
        sort(sorted_values.begin(), sorted_values.end());
        sorted_values.erase(unique(sorted_values.begin(), sorted_values.end()), sorted_values.end());
        max_rank = sorted_values.size();

        bit_count.assign(max_rank + 1, 0);
        bit_sum.assign(max_rank + 1, 0);

        auto get_rank = [&](int val) {
            return lower_bound(sorted_values.begin(), sorted_values.end(), val) - sorted_values.begin() + 1;
        };

        int target_k = k - 1;                     // we need k‑1 additional starts

        // initialise the window (first `dist + 1` elements, but not beyond the array)
        for (int i = 1; i <= min(dist, n - 1); ++i) {
            update(get_rank(nums[i]), 1, nums[i]);
        }

        long long min_cost = nums[0] + query(target_k);

        // slide the window across the array
        for (int i = 2; i + dist < n; ++i) {
            // remove element leaving the window
            update(get_rank(nums[i - 1]), -1, -nums[i - 1]);
            // add new element entering the window
            update(get_rank(nums[i + dist]), 1, nums[i + dist]);

            long long cur = nums[0] + query(target_k);
            min_cost = min(min_cost, cur);
        }
        return (int)min_cost;
    }
};

Python

def minCost(nums, k, dist):
    n = len(nums)

    # ---- coordinate compression ----
    sorted_unique = sorted(set(nums))
    ranks = {val: i + 1 for i, val in enumerate(sorted_unique)}
    max_rank = len(sorted_unique)

    bit_count = [0] * (max_rank + 1)   # how many numbers of each rank
    bit_sum   = [0] * (max_rank + 1)   # sum of those numbers

    def update(rank: int, c_delta: int, v_delta: int) -> None:
        while rank <= max_rank:
            bit_count[rank] += c_delta
            bit_sum[rank]   += v_delta
            rank += rank & -rank

    def query(target: int) -> int:
        idx = 0
        cur_k = 0
        cur_s = 0
        i = max_rank.bit_length()
        while i >= 0:
            next_idx = idx + (1 << i)
            if next_idx <= max_rank and cur_k + bit_count[next_idx] < target:
                idx   = next_idx
                cur_k += bit_count[next_idx]
                cur_s += bit_sum[next_idx]
            i -= 1
        return cur_s + (target - cur_k) * sorted_unique[idx]

    target_k = k - 1

    # initialise the window (first `dist + 1` elements, but not beyond the array)
    for i in range(1, min(dist + 1, n)):
        update(ranks[nums[i]], 1, nums[i])

    min_cost = nums[0] + query(target_k)

    # slide the window across the array
    for i in range(2, n - target_k + 1):
        # remove the element that leaves the window
        update(ranks[nums[i - 1]], -1, -nums[i - 1])
        # add the new element entering the window
        update(ranks[nums[i + dist]], 1, nums[i + dist])

        cur = nums[0] + query(target_k)
        min_cost = min(min_cost, cur)

    return min_cost

Source: …

1])

        # add the new element that enters the window (if any)
        if i + dist < n:
            update(ranks[nums[i + dist]], 1, nums[i + dist])

        cur = nums[0] + query(target_k)
        min_cost = min(min_cost, cur)

    return min_cost

JavaScript（Node.js）

function minCost(nums, k, dist) {
    const n = nums.length;

    // ---- coordinate compression ----
    const sortedUnique = Array.from(new Set(nums)).sort((a, b) => a - b);
    const ranks = new Map();
    sortedUnique.forEach((val, i) => ranks.set(val, i + 1));
    const maxRank = sortedUnique.length;

    const bitCount = new Array(maxRank + 1).fill(0);
    const bitSum   = new Array(maxRank + 1).fill(0n); // use BigInt for safety

    const update = (rank, cDelta, vDelta) => {
        while (rank <= maxRank) {
            bitCount[rank] += cDelta;
            bitSum[rank]   += BigInt(vDelta);
            rank += rank & -rank;
        }
    };

    const query = (target) => {
        let idx = 0, curK = 0, curS = 0n;
        for (let i = Math.floor(Math.log2(maxRank)); i >= 0; i--) {
            const nextIdx = idx + (1 << i);
            if (nextIdx <= maxRank && curK + bitCount[nextIdx] < target) {
                idx   = nextIdx;
                curK += bitCount[nextIdx];
                curS += bitSum[nextIdx];
            }
        }
        const remaining = target - curK;
        return curS + BigInt(remaining) * BigInt(sortedUnique[idx]);
    };

    const targetK = k - 1;

    // initialise the window (first `dist + 1` elements, but not beyond the array)
    for (let i = 1; i <= Math.min(dist, n - 1); i++) {
        update(ranks.get(nums[i]), 1, nums[i]);
    }

    let minCost = BigInt(nums[0]) + query(targetK);

    // slide the window across the array
    for (let i = 2; i + dist < n; i++) {
        // remove element leaving the window
        update(ranks.get(nums[i - 1]), -1, -nums[i - 1]);
        // add new element entering the window
        update(ranks.get(nums[i + dist]), 1, nums[i + dist]);

        const cur = BigInt(nums[0]) + query(targetK);
        if (cur < minCost) minCost = cur;
    }

    return Number(minCost);
}

关键技术

坐标压缩

当数值范围（最高可达 10^9 或更大）远大于元素数量 n 时，我们将每个不同的数值映射到一个紧凑的秩。这样就可以把秩用作数组（例如 Fenwick 树）的索引。

双 Fenwick 树

一个 BIT 存储元素的 计数，另一个 BIT 存储它们的 和值。两者结合可以快速实现“前 K 小元素之和”查询。

BIT 上的二进制提升

我们不使用线性扫描或在 BIT 上的二分查找，而是采用二进制提升定位累计计数首次达到（或超过）K 的前缀。这样将搜索时间降低到 O(log maxRank)。

为什么这很重要

这个问题是处理 流式数据 并且时间限制紧迫的经典例子：

  • 在真实系统中（例如高频交易平台），你经常需要获取 “最近 T 分钟内的最佳 K 个价格”。

  • 使用滑动窗口结合一种秩统计数据结构（双树状数组）可以提供所需的高效性。

  • 虽然该问题看起来像是一个 “困难” 挑战，但将其拆解为：

    1. 窗口管理，以及
    2. 高效的基于秩的查询

    可以使解法既易于理解又易于实现。

Back to Blog

相关文章

阅读更多 »

第10题：去重

问题描述：我们需要一个函数，从列表中删除重复项，同时保留元素的原始顺序。例如 remove_duplicates(1, 2, 2, 3)。