题解：

这道题是一个带权匹配问题，可以通过构建最小生成树来解决。以下是详细的题解分析。

问题分析：

我们有 N 件物品，每件物品有两种运输方式：

1. 单独运输：费用为 A[i]
2. 配对运输：费用为 B[i] + B[j]，需要满足 |W[i] - W[j]| ≤ D

由于 B[i] < A[i]，我们总是希望尽可能配对运输以节省费用。

关键观察

1. 排序重要性：将物品按重量 W 排序后，可配对的物品一定是连续的（因为重量差限制 D）。
2. 配对结构：对于排序后的物品，如果 i 和 j 配对（i < j），那么区间 [i, j] 内的所有物品也必须配对（形成若干对）。
3. 图论模型：我们可以构建一个带权完全图：
   • 每个节点对应一个物品
   • 节点 i 有一个自环，权重为 A[i]（表示单独运输）
   • 节点 i 和 j 之间有一条边，权重为 B[i] + B[j]（表示配对运输），但这条边只有在 |W[i] - W[j]| ≤ D 时才存在

解法思路：

对于固定的 D，问题等价于在带限制的图中找最小生成森林：

• 每个连通分量要么是单个节点（单独运输），要么是一对节点（配对运输）
• 由于每艘船最多运两件，所以没有更大的连通分量

动态规划解法（对于固定 D）

设 dp[i] 表示处理完前 i 个物品（排序后）的最小费用：

1. 物品 i 单独运输：dp[i] = dp[i-1] + A[i]
2. 物品 i 与 i-1 配对（如果 |W[i] - W[i-1]| ≤ D）： dp[i] = min(dp[i], dp[i-2] + B[i] + B[i-1])

对于每个 D，我们可以 O(N) 计算答案。但 Q 最大可达 10^5，不能对每个 D 都重新计算。

关键优化：离线处理

注意到 D 越大，可配对的边越多，总费用越小（单调不减）。我们可以：

1. 计算所有可能的配对边（i, j，其中 i < j）的"激活阈值" D_ij = |W[i] - W[j]|
2. 当 D ≥ D_ij 时，边 (i, j) 可用
3. 随着 D 增加，可用边增多，费用减少

算法步骤

1. 预处理：

   • 将物品按重量 W 排序
   • 计算所有相邻物品的配对边（i, i+1），因为最优配对通常是相邻的

2. Kruskal-like 算法：

   • 将所有可能的边（只考虑相邻物品）按 |W[i] - W[j]| 排序
   • 初始状态：所有物品单独运输，总费用 = sum(A)
   • 按 D 从小到大处理边，当 D 达到边的权重时，考虑合并两个物品
   • 维护当前最小费用

3. 并查集优化：

   • 使用并查集维护当前哪些物品已配对
   • 每个集合要么是单个物品，要么是一对物品
   • 合并时更新总费用：减少 A[i]+A[j]，增加 B[i]+B[j]

时间复杂度

• 排序：O(N log N)
• 边排序：O(N log N)（只考虑相邻物品）
• 查询处理：O((N+Q) log N)

C 实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAXN 100010

typedef struct {
    int w, a, b;
} Item;

typedef struct {
    int diff, idx;
} Edge;

typedef struct {
    int d, idx;
} Query;

Item items[MAXN];
Edge edges[MAXN];
Query queries[MAXN];
long long answers[MAXN];

int parent[MAXN], size[MAXN];

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int cmp_item(const void *a, const void *b) {
    return ((Item*)a)->w - ((Item*)b)->w;
}

int cmp_edge(const void *a, const void *b) {
    return ((Edge*)a)->diff - ((Edge*)b)->diff;
}

int cmp_query(const void *a, const void *b) {
    return ((Query*)a)->d - ((Query*)b)->d;
}

int64_t calculate_costs(int* W, int* A, int* B, int* E, int N, int Q) {
    // 初始化物品
    for (int i = 0; i < N; i++) {
        items[i].w = W[i];
        items[i].a = A[i];
        items[i].b = B[i];
    }
    
    // 按重量排序
    qsort(items, N, sizeof(Item), cmp_item);
    
    // 计算初始总费用（全部单独运输）
    int64_t total = 0;
    for (int i = 0; i < N; i++) {
        total += items[i].a;
    }
    
    // 构建边（只考虑相邻物品，这是最优的）
    for (int i = 0; i < N - 1; i++) {
        edges[i].diff = items[i+1].w - items[i].w;
        edges[i].idx = i;
    }
    
    // 按重量差排序边
    qsort(edges, N-1, sizeof(Edge), cmp_edge);
    
    // 处理查询
    for (int i = 0; i < Q; i++) {
        queries[i].d = E[i];
        queries[i].idx = i;
    }
    qsort(queries, Q, sizeof(Query), cmp_query);
    
    // 初始化并查集
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    
    // 当前处理的边索引
    int edge_idx = 0;
    
    // 处理每个查询
    for (int q = 0; q < Q; q++) {
        int d = queries[q].d;
        
        // 激活所有满足条件的边
        while (edge_idx < N - 1 && edges[edge_idx].diff <= d) {
            int i = edges[edge_idx].idx;
            int j = i + 1;
            
            // 检查是否可以配对
            int root_i = find(i);
            int root_j = find(j);
            
            // 如果两个物品都未配对，则配对它们
            if (root_i != root_j && size[root_i] == 1 && size[root_j] == 1) {
                // 更新总费用
                total -= items[i].a + items[j].a;
                total += items[i].b + items[j].b;
                
                // 合并集合
                if (root_i < root_j) {
                    parent[root_j] = root_i;
                    size[root_i] = 2;
                } else {
                    parent[root_i] = root_j;
                    size[root_j] = 2;
                }
            }
            
            edge_idx++;
        }
        
        answers[queries[q].idx] = total;
    }
    
    return (int64_t)answers;
}

算法正确性证明

1. 最优配对性质：在排序后的物品序列中，最优配对不会交叉。即如果 i 与 j 配对，k 与 l 配对，且 i < k < j < l，那么这不是最优的。
2. 相邻配对最优性：最优解中，配对的物品在排序后的序列中一定是相邻的，或者可以通过调整变成相邻而不增加费用。
3. 单调性：随着 D 增大，可用边增多，总费用单调不减（实际是单调不增）。

注意事项

1. 数据类型：总费用可能很大，需要使用 64 位整数（long long）。
2. 边界情况：N=1 时，只能单独运输。
3. 查询排序：通过离线处理，我们可以一次处理所有查询，避免重复计算。

这个算法可以在 O((N+Q) log N) 时间内解决本题，满足题目约束条件。