[OII 2025] 木材运输 / Trasporto tronchi

题目分析

题意概述

• 有 $N$ 棵树，初始位置为严格递增的数组 $A$，卡车位于位置 $0$，需将所有树运至 $0$ 点。
• 修剪一棵树的成本为 $K$，修剪后的树可在连续的修剪树上方滚动（移动规则特殊）。
• 移动方式：
  1. 普通移动：任意树向左移 1 格（需空位），代价 1（未修剪树仅支持此方式）。
  2. 滚动移动：修剪树沿连续修剪树向左滚动至空位，无论距离代价均为 1（大幅降低长距离移动成本）。
• 目标：最小化总代价（修剪成本 + 移动成本）。

关键洞察

1. 顺序不变性：树无法交叉穿过，初始位置递增意味着移动过程中始终保持 $A_0 < A_1 < \dots < A_{N-1}$ 的相对顺序。
2. 修剪有效性：仅连续修剪的树段能产生滚动收益（非连续修剪无法形成滚动链，修剪成本无意义）。
3. 代价计算核心：
   • 未修剪树的移动代价 = 自身初始位置（需移动 $A_i$ 步到 0）。
   • 连续修剪树段 $[i..j]$ 的移动代价 = $A_j$（整个段可整体滚动，总步数等价于最右侧树的位置）。
   • 修剪收益 = （原移动成本总和 - 修剪后移动成本） - 修剪成本。

算法推导

1. 基础代价计算

2. 修剪收益公式

• 原移动成本：$\sum_{k=i}^j A_k$（每棵树独立移动）。
• 修剪后移动成本：$A_j$（整体滚动）。
• 修剪成本：$K \times (j - i + 1)$（修剪段内所有树）。
• 收益 = （原成本 - 修剪后成本） - 修剪成本 = $\left( \sum_{k=i}^j A_k - A_j \right) - K \times (j - i + 1) = \sum_{k=i}^{j-1} A_k - K \times (j - i + 1)$。

3. 前缀和优化

• 定义 $\text{prefix}[0] = 0$，$\text{prefix}[m] = A_0 + A_1 + \dots + A_{m-1}$（前 $m$ 棵树的和）。
• $\sum_{k=i}^{j-1} A_k = \text{prefix}[j] - \text{prefix}[i]$。

4. 收益最大化转化

• $B[j] = \text{prefix}[j] - K \times (j + 1)$（仅与 $j$ 相关）。
• $C[i] = \text{prefix}[i] - K \times i$（仅与 $i$ 相关）。

5. 算法步骤

1. 计算所有树不修剪的总代价 $S = \sum A_i$。
2. 遍历数组，实时维护：
   • 前缀和 $\text{prefix}_j$（避免存储完整前缀和数组，节省空间）。
   • 最小 $C[i]$（$\min_C$）。
   • 最大收益 $\max_{\text{gain}}$。
3. 最终最小代价 = $S - \max(\max_{\text{gain}}, 0)$（收益为负时不修剪，取 0）。

Code

#include <iostream>
#include <vector>

using namespace std;

long long carica(int N, int K, vector<int> A) {
    long long sum_A = 0;
    for (int x : A) {
        sum_A += x;
    }
    if (N == 0) {
        return 0;
    }
    long long prefix_j = 0;
    long long min_C = 0; // C[0] = prefix[0] - K*0 = 0
    long long max_gain = -1LL * K; // B[0] - C[0] = (0 - K*1) - 0 = -K（修剪第0棵树的收益）
    for (int j = 1; j < N; ++j) {
        prefix_j += A[j-1];
        long long current_C = prefix_j - 1LL * K * j;
        if (current_C < min_C) {
            min_C = current_C;
        }
        long long current_B = prefix_j - 1LL * K * (j + 1);
        long long current_gain = current_B - min_C;
        if (current_gain > max_gain) {
            max_gain = current_gain;
        }
    }
    max_gain = max(max_gain, 0LL); // 收益为负时不修剪
    return sum_A - max_gain;
}

// GRADER DI ESEMPIO, NON MODIFICARE

#ifndef ONLINE_JUDGE

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> A(N);
    for (int &a: A) cin >> a;

    cout << carica(N, K, A) << endl;

    return 0;
}

#endif

代码解释

核心函数 carica

1. 基础求和：计算所有树不修剪时的总移动代价 sum_A。
2. 初始化：
   • prefix_j：初始为 0（对应 prefix[0]），实时累计前 $j$ 棵树的和。
   • min_C：初始为 C[0] = 0（$i=0$ 时的 $C[i]$ 值）。
   • max_gain：初始为 -K（修剪单棵树 $[0..0]$ 的收益，避免遗漏单棵树修剪的情况）。
3. 遍历优化：
   • 对每个 $j$（从 1 到 $N-1$），更新前缀和 prefix_j。
   • 计算当前 $C[j]$ 并更新 min_C（确保始终保存 $i \leq j$ 中最小的 $C[i]$）。
   • 计算当前 $B[j]$ 和对应的最大收益，更新 max_gain。
4. 结果计算：收益为负时不修剪（取 max(max_gain, 0)），总代价 = 基础代价 - 最大收益。

主函数 main

• 输入处理：用 scanf 高效读取输入（避免 cin 的同步开销，适配大数据规模）。
• 函数调用：调用 carica 计算最小代价。
• 输出结果：用 printf 输出长整型结果（%lld 适配 long long）。

复杂度分析

• 时间复杂度：$O(N)$，仅线性遍历数组一次，无嵌套循环。
• 空间复杂度：$O(N)$，仅存储输入数组 $A$（前缀和实时计算，无额外数组开销）。