思路

这是一个典型的贪心策略问题。为了使得总成本最小，我们应该优先使用价格最低的发货日期。

问题的关键在于，一个订单有多个可选的发货日期（只要在最晚发货日期之前），而一个发货日期也可以被多个订单使用（只要不超过当天的发货上限）。

一个直观且正确的贪心思路是按时间顺序来处理。我们从第 1 天开始，一直到第 $n$ 天。在每一天 $i$，我们会遇到两件事：

1. 新的发货机会：当天有 $x$ 个包裹的额度，每个包裹的单价是 $a_i$。
2. 新的发货需求：有一批订单的最晚发货日期是今天。这些订单必须在今天或今天之前发货。

为了做出最优决策，我们可以在第 $i$ 天时，考虑所有“已解锁”的发货机会（即第 1 天到第 $i$ 天的所有发货额度），并将它们视为一个“成本池”。然后，对于所有最晚发货日期为第 $i$ 天的订单，我们从这个成本池中为它们挑选成本最低的发货机会。

这个过程可以用一个最小优先队列（小顶堆）来高效实现。

具体算法步骤如下：

1. 预处理订单：我们首先遍历所有 $m$ 个订单，统计出在每一天 $i$（从 1 到 $n$）有多少个订单的最晚发货日期是当天。我们可以用一个数组 orders_due[i] 来记录这个数量。

2. 贪心选择：我们从第 1 天遍历到第 $n$ 天。

   • 维护一个最小优先队列 pq，用来存放所有可用的发货机会（我们称之为“槽位”），按发货成本从小到大排序。
   • 在第 $i$ 天，我们将当天的 $x$ 个发货槽位（每个成本为 $a_i$）加入到优先队列 pq 中。
   • 然后，我们处理当天到期的订单，数量为 orders_due[i]。这些订单必须在第 $i$ 天或之前发货。此时，优先队列 pq 中存放的是第 1 天到第 $i$ 天所有可用的、并且还未被占用的发货槽位。
   • 为了成本最小化，我们为这 orders_due[i] 个订单分配当前 pq 中成本最低的槽位。具体操作就是从 pq 中取出（pop）orders_due[i] 个成本最低的元素，并将这些成本累加到总成本 total_cost 中。

3. 结果：遍历完 $n$ 天后，total_cost 就是我们要求的最小总发货成本。由于题目保证有解，所以在为订单分配槽位时，优先队列一定不会为空。

为了优化空间和时间，当一天的发货量上限 $x$ 很大时，我们不必真的向优先队列中添加 $x$ 个相同的价格。我们可以添加一个数对 (价格, 数量)，表示有 数量 个成本为 价格 的槽位。当需要分配槽位时，我们取出成本最低的数对，按需分配，如果该数对的槽位没有用完，再将更新了数量的数对放回优先队列。

C++

#include <iostream>
#include <vector>
#include <queue>

// 使用 pair 来存储 {价格, 数量}
using P = std::pair<long long, int>;

int main() {
    // 加速 C++ IO
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, x;
    std::cin >> n >> m >> x;

    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // orders_due[i] 存储最晚发货日期为第 i+1 天的订单数量
    std::vector<int> orders_due(n, 0);
    for (int i = 0; i < m; ++i) {
        int b;
        std::cin >> b;
        // 转换为 0-based 索引
        orders_due[b - 1]++;
    }

    // 最小优先队列（小顶堆），存储可用的发货槽位 {价格, 数量}
    // std::greater<P> 使其按 pair 的第一个元素（价格）升序排序
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

    long long total_cost = 0;

    // 从第 1 天到第 n 天遍历
    for (int i = 0; i < n; ++i) {
        // 将当天的发货槽位加入优先队列
        pq.push({a[i], x});

        // 获取当天必须发货的订单数量
        int orders_to_ship = orders_due[i];

        // 为这些订单分配成本最低的槽位
        while (orders_to_ship > 0) {
            // 取出当前最便宜的槽位信息
            P top = pq.top();
            pq.pop();
            long long cost = top.first;
            int count = top.second;

            // 决定使用多少个这种价格的槽位
            int num_to_use = std::min(orders_to_ship, count);

            // 累加成本
            total_cost += num_to_use * cost;
            
            // 更新剩余需要发货的订单数量
            orders_to_ship -= num_to_use;
            
            // 如果这种价格的槽位还有剩余，将其放回优先队列
            if (count > num_to_use) {
                pq.push({cost, count - num_to_use});
            }
        }
    }

    std::cout << total_cost << std::endl;

    return 0;
}

Python

import heapq
import sys

def solve():
    # 读取输入
    n, m, x = map(int, sys.stdin.readline().split())
    prices = list(map(int, sys.stdin.readline().split()))
    deadlines = list(map(int, sys.stdin.readline().split()))

    # orders_due[i] 存储最晚发货日期为第 i+1 天的订单数量
    orders_due = [0] * n
    for d in deadlines:
        # 转换为 0-based 索引
        orders_due[d - 1] += 1
    
    # 最小优先队列（小顶堆），存储可用的发货槽位 (价格, 数量)
    pq = []
    
    total_cost = 0
    
    # 从第 1 天到第 n 天遍历
    for i in range(n):
        # 将当天的发货槽位加入优先队列
        # heapq 默认是小顶堆，元组会按第一个元素（价格）排序
        heapq.heappush(pq, (prices[i], x))
        
        # 获取当天必须发货的订单数量
        orders_to_ship = orders_due[i]
        
        # 为这些订单分配成本最低的槽位
        while orders_to_ship > 0:
            # 取出当前最便宜的槽位信息
            cost, count = heapq.heappop(pq)
            
            # 决定使用多少个这种价格的槽位
            num_to_use = min(orders_to_ship, count)
            
            # 累加成本
            total_cost += num_to_use * cost
            
            # 更新剩余需要发货的订单数量
            orders_to_ship -= num_to_use
            
            # 如果这种价格的槽位还有剩余，将其放回优先队列
            if count > num_to_use:
                heapq.heappush(pq, (cost, count - num_to_use))

    print(total_cost)

solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 加速 Java IO
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        // ordersDue[i] 存储最晚发货日期为第 i+1 天的订单数量
        int[] ordersDue = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int b = Integer.parseInt(st.nextToken());
            // 转换为 0-based 索引
            ordersDue[b - 1]++;
        }

        // 最小优先队列（小顶堆），存储可用的发货槽位 {价格, 数量}
        // 按数组的第一个元素（价格）升序排序
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(arr -> arr[0]));

        long totalCost = 0;

        // 从第 1 天到第 n 天遍历
        for (int i = 0; i < n; i++) {
            // 将当天的发货槽位加入优先队列
            pq.offer(new long[]{a[i], x});

            // 获取当天必须发货的订单数量
            int ordersToShip = ordersDue[i];

            // 为这些订单分配成本最低的槽位
            while (ordersToShip > 0) {
                // 取出当前最便宜的槽位信息
                long[] top = pq.poll();
                long cost = top[0];
                long count = top[1];

                // 决定使用多少个这种价格的槽位
                long numToUse = Math.min(ordersToShip, count);
                
                // 累加成本
                totalCost += numToUse * cost;

                // 更新剩余需要发货的订单数量
                ordersToShip -= numToUse;
                
                // 如果这种价格的槽位还有剩余，将其放回优先队列
                if (count > numToUse) {
                    pq.offer(new long[]{cost, count - numToUse});
                }
            }
        }
        
        System.out.println(totalCost);
    }
}

题目内容

多多有一批订单需要发货，每个订单都存在独立的最晚发货日期，需要在那之前发出。

多多找了一家合作的物流商，物流商给出了未来一段时间每天的发货价格，并且每天最多能发的包裹数量是有限的。

多多需要在每个订单的最晚发货日期前将所有订单发出，并尽可能减少发货成本。

请你帮多多计算一下最小的发货成本是多少。

输入描述

第一行有三个整数 $n, m, x(1≤n,m,x≤10^5)$ ，代表物流商给出了接下来 $n$ 天的发货价格，有 $m$ 个订单需要发货，每天最多能发 $x$ 个包裹。

第二行有 $n$ 个整数 $a_1,a_2,...,a_n(0 ≤ a_i≤ 10^9,1 ≤i≤ n)$，代表第 $i$ 天发一包要的价格为 $a_i$ 。

第三行有 $m$ 个整数 $b_1,b_2,...,b_n(1 ≤ b_j≤ n,1 ≤j≤ m)$ ，代表订单 $j$ 需要在第 $b_j$ 天以及之前发货。

(输入数据保证在 $n$ 天内可以将所有订单发完)

输出描述

输出一个整数，表示最小的发货成本。

样例1

输入

3 4 2
3 2 1
1 2 2 3

输出

8

说明

第一天将订单$_1$发货，花费 $3$

第一天将订单$_2$和订单$_3$发货，花费 $4$

第二天将订单$_4$发货，花费 $1$

总共花费 $8$