题解

分析题意后发现，要从起点到终点，最终会买 $n - 1$ 个单位的物质，那么我只需要判断，当前从 $i$ 到 $i + 1$ 这一步转移所需要的物资从哪个城邦买即可。

做法

​ 维护一个单调队列 $queue$，其中购买物资的价格依次上升。

​ 假设当前要从第 $i$ 个城邦走到第 $i + 1$ 个城邦，并且打算从第 $j$ 个城邦买当前转移的所需的物资（单位1），那么此时的花费为 $i - j + cost[j]$，如果此时从第 $j$ 买物资花费要大于 $cost[i]$ （即从第 $i$ 个城邦买单位 $1$ 的物资），那么对于所有的 $k \in [i, n - 1]$，要从第 $k$ 个 城邦走到第 $k + 1$ 个城邦所购买的物资一定是从 $i$ 购买要优于从 $j$，那么此时的 $j$ 对后面所有城邦都不会造成贡献了，此时直接在队列中删去即可。

时间复杂度：$O(n)$

AC代码

• Cpp

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;


int main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<int> cost(n);
    for(int & i : cost) cin >> i;
    queue<int> q;
    q.push(0);
    LL s = cost[0];
    for(int i = 1; i < n - 1; i ++)
    {
    	while(q.size() && cost[q.front()] + i - q.front() >= cost[i]) // 如果从当前 i 买物资比之前更划算了
    		q.pop(); // 直接删去之前的即可
    	q.push(i);
    	s += cost[q.front()] + i - q.front(); // 最划算的一个
    }
    cout << s << "\n";
    return 0;
}

• Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] cost = new int[n];
        for (int i = 0; i < n; i++) {
            cost[i] = scanner.nextInt();
        }
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        long s = cost[0];
        for (int i = 1; i < n - 1; i++) {
            while (!q.isEmpty() && cost[q.peek()] + i - q.peek() >= cost[i]) {// 如果从当前 i 买物资比之前更划算了
                q.poll(); // 直接删去之前的即可
            }
            q.offer(i);
            s += cost[q.peek()] + i - q.peek();
        }
        System.out.println(s);
    }
}

• Python

from collections import deque

n = int(input())
cost = list(map(int, input().split()))
q = deque([0])
s = cost[0]
for i in range(1, n - 1):
    while q and cost[q[0]] + i - q[0] >= cost[i]: #  如果从当前 i 买物资比之前更划算了
        q.popleft() // 直接删去之前的即可
    q.append(i)
    s += cost[q[0]] + i - q[0]

print(s)

题目名称

小红的物资调度

问题描述

在一片被战争蹂躏的土地上，小红被指派完成一项艰巨的任务：他要从联盟的首都出发，确保重要的物资安全运送到最前线的最后一个要塞。联盟的城邦沿着补给线线性排列，小红需要精心筹划在每个城邦的物资购买与运输计划。

从一个城邦到达相邻城邦会消耗一定量的物资。每个城邦都有物资出售，但价格不尽相同。小红可以根据需要在任何城邦购买任意数量的物资。不过，如果小红携带的物资超过基本需求量(基本需求量为1)，将会产生额外的运输成本，即每多携带一单位物资跨越到下一个城邦，就需要支付一单位的运输费。

小红希望以最低的成本安全抵达最后一个城邦。请计算小红完成任务所需的最小总花费。

输入格式

第一行包含一个正整数 $n$，代表城邦的个数。

第二行包含 $n$ 个由空格分隔的正整数 $p_1, p_2, ..., p_n$，代表沿途每个城邦的物资售价。

输出格式

输出一个整数，表示小红抵达最后一个城邦的最小总花费。

样例输入

4
1 3 2 4

样例输出

5

样例说明

在第 1 个城邦购买 2 单位物资，花费为 $1 \times 2 = 2$。

将 1 单位物资从第1个城邦运送到第 2 个城邦，花费为 1。

在第 2 个城邦不购买物资，因此花费为 0。

在第 3 个城邦购买 1 单位物资，花费为 $2 \times 1 = 2$。

总花费为物资购买成本加上运输成本，即 $2 + 1 + 2 = 5$。

评测数据与规模

对于 $100\%$ 的评测数据，满足 $1 \leq n \leq 10^5$，$1 \leq p_i \leq 10^9$。