题目大意

P16229 [蓝桥杯 2026 省 A] 外卖配送

题目描述

午高峰的外卖站点里，骑手小蓝正紧盯着屏幕上待处理的 $N$ 个订单。这些订单必须严格按照系统列表中的固定顺序依次配送，不可打乱或跳过。为了顺利完成任务，小蓝计划将这 $N$ 个订单分成若干个批次进行配送。

站点内停放着 $M$ 种不同的交通工具，每种工具都具备两个属性：平均路途耗时 $A_i$ 和箱体拥挤系数 $B_i$。对于每一个批次，小蓝可以根据该批次订单的数量，从 $M$ 种工具中独立选择一种最合适的。

假设某一个批次包含 $L$ 个订单，且小蓝选用第 $i$ 种交通工具，则该批次的总耗时由以下三部分组成：

1. 路途耗时：$L \times A_i$ 秒。

2. 取餐耗时：由于箱内挤压，整理 $L$ 个订单需处理 $\frac{L(L-1)}{2}$ 对挤压关系，每对耗时 $B_i$，共计 $\frac{L(L-1)}{2} \times B_i$ 秒。

3. 折返耗时：分批配送存在额外的折返成本。处理第一个批次时，由于小蓝默认已在站点装车完毕可以直接出发，此项耗时为 $0$ 秒；但从第二个批次开始，每开启一个新的批次，都必须花费固定的 $X$ 秒用于返回站点装载下一批订单。

现在，请你帮助小蓝规划最优的分批方案，并计算出送完 $N$ 个订单所需的最小总耗时。

输入格式

一行包含三个整数 $N$、$M$ 和 $X$，分别表示订单总数、交通工具的种类数，以及固定耗时。

接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，依次表示第 $i$ 种交通工具的平均路途耗时与箱体拥挤系数。

输出格式

输出一个整数，表示完成全部 $N$ 个订单配送任务所需的最小总耗时（单位：秒）。

输入输出样例 #1

输入 #1

5 2 40
10 8
2 20

输出 #1

118

说明/提示

【样例说明】

一种最优的方案是分成 $2$ 批配送：

阶段	详情	耗时
第 $1$ 批（$2$ 单，选工具 $2$）	路途 $2 \times 2 = 4$；取餐 $\frac{2 \times 1}{2} \times 20 = 20$	$24$ 秒
折返	固定耗时	$40$ 秒
第 $2$ 批（$3$ 单，选工具 $1$）	路途 $3 \times 10 = 30$；取餐 $\frac{3 \times 2}{2} \times 8 = 24$	$54$ 秒
合计	<	$\mathbf{118}$ 秒

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N, M \le 100$；

对于所有评测用例，$1 \le N, M \le 5000$，$1 \le X, A_i, B_i \le 10^9$。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing, arrows.meta}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

% --- TikZ 颜色定义 ---
\definecolor{batch}{RGB}{50,120,200}     % 蓝色 — 批次
\definecolor{vehicle}{RGB}{220,80,60}    % 红色 — 交通工具
\definecolor{dp}{RGB}{0,160,80}          % 绿色 — DP 转移
\definecolor{knapsack}{RGB}{140,80,200}  % 紫色 — 背包物品
\definecolor{highlight}{RGB}{255,160,0}  % 橙色 — 高亮

\title{\textbf{P16229 [蓝桥杯 2026 省 A] 外卖配送} \\ 题解}
\author{}
\date{}

\begin{document}
\maketitle

\section{题意概述}

将 $N$ 个订单按固定顺序分成若干批次依次配送。站点有 $M$ 种交通工具，第 $i$ 种的路途耗时为 $A_i$，箱体拥挤系数为 $B_i$。若某批次包含 $L$ 个订单且选用第 $i$ 种交通工具，该批次耗时为：
$$L \cdot A_i + \frac{L(L-1)}{2} \cdot B_i$$
此外，从第二个批次起，每开启一个新批次需额外花费固定的 $X$ 秒折返。求送完所有订单的最小总耗时。

\section{第一层思考：预处理单批次最优耗时}

先不考虑批次之间的分配问题，聚焦一个子问题：如果某批次恰好要送 $L$ 个订单，最少要花多少时间？

交通工具的选择仅取决于 $L$，与其他批次无关。因此，对于每个 $L$，我们遍历所有 $M$ 种交通工具，取最小耗时即可。定义：
$$C_L = \min_{1 \le i \le M} \left( L \cdot A_i + \frac{L(L-1)}{2} \cdot B_i \right)$$

$C_L$ 的含义是：单独配送一个包含 $L$ 个订单的批次所需的最小耗时（不含折返）。这一步的时间复杂度为 $O(NM)$。

\section{第二层思考：发现完全背包结构}

现在的问题变成了：将 $N$ 个订单分成若干批，第一批不需要折返，后续每批额外花费 $X$ 秒。怎样分批使得总耗时最小？

\subsection{统一折返代价的技巧}

为了让每一批的代价形式一致，我们使用一个常见技巧：\textbf{假设每一批都需要折返}（每批的代价统一为 $C_L + X$），最终答案再减去多算的第一批的那一次 $X$。

这样，每一批的代价就只取决于该批的订单数 $L$，是一个"物品"的概念了。

\subsection{转化为完全背包}

经过上述统一，问题可以精确地描述为：

\begin{quote}
有 $N$ 种"物品"，第 $L$ 种物品的"重量"为 $L$，"代价"为 $C_L + X$。每种物品可以使用任意多次。需要恰好装满容量为 $N$ 的背包，求最小总代价。
\end{quote}

这正是一个\textbf{完全背包问题}。定义状态 $f_w$ 为恰好配送前 $w$ 个订单的最小总耗时（含统一折返），转移方程为：
$$f_w = \min_{1 \le L \le w} \left( f_{w - L} + C_L + X \right)$$
初始条件 $f_0 = 0$，最终答案为 $f_N - X$。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.75, every node/.style={font=\small}]
	% 订单序列
	\foreach \i in {1,...,10} {
		\fill[gray!15] (\i-0.45, -0.4) rectangle (\i+0.45, 0.4);
		\draw[gray!60] (\i-0.45, -0.4) rectangle (\i+0.45, 0.4);
		\node at (\i, 0) {$\i$};
	}
	\node[font=\bfseries] at (5.5, 1) {$N = 10$ 个订单};

	% 分批
	\draw[batch, line width=2.5pt] (0.45, -0.6) -- (3.55, -0.6);
	\node[batch, font=\bfseries] at (2, -1.1) {第 1 批 ($L=3$)};

	\draw[vehicle, line width=2.5pt] (3.55, -0.6) -- (7.55, -0.6);
	\node[vehicle, font=\bfseries] at (5.5, -1.1) {第 2 批 ($L=4$)};

	\draw[dp, line width=2.5pt] (7.55, -0.6) -- (10.55, -0.6);
	\node[dp, font=\bfseries] at (9, -1.1) {第 3 批 ($L=3$)};

	% 代价标注
	\node[batch] at (2, -1.7) {$C_3 + X$};
	\node[vehicle] at (5.5, -1.7) {$C_4 + X$};
	\node[dp] at (9, -1.7) {$C_3 + X$};

	% 总代价
	\node[font=\bfseries] at (5.5, -2.5) {总代价 $= (C_3 + X) + (C_4 + X) + (C_3 + X) - X$};
\end{tikzpicture}
\caption{%
	将 $10$ 个订单分成 $3$ 批的示意图。每批统一计入折返代价 $X$，最后减去首批多算的一次 $X$。批次大小 $L$ 对应完全背包中的"物品重量"。%
}
\label{fig:batch}
\end{figure}

\subsection{完全背包的代码范式}

标准的完全背包写法是：外层枚举物品种类 $L$，内层从 $L$ 到 $N$ 正序枚举容量 $w$。正序枚举保证了同一种物品可以被重复选取：

\begin{minted}{cpp}
for (int L = 1; L <= N; ++L)
	for (int w = L; w <= N; ++w)
		dpN[w] = min(dpN[w], dp[L] + dpN[w - L] + X);
\end{minted}

这和 0-1 背包的唯一区别就在于内层循环是\textbf{正序}而非逆序。

\section{关于完全背包时间复杂度的讨论}

读者可能会注意到：这道题的 DP 部分是一个双重循环，时间复杂度为 $O(N^2)$。这和"完全背包的时间复杂度是 $O(nW)$"（$n$ 为物品种类数，$W$ 为背包容量）是一致的吗？

答案是\textbf{完全一致}的。

在本题中，"物品"是批次大小 $L \in \{1, 2, \ldots, N\}$，共有 $n = N$ 种物品；"背包容量"$W = N$（需要恰好配送 $N$ 个订单）。所以完全背包的时间复杂度 $O(nW) = O(N \times N) = O(N^2)$，恰好与代码中双重循环的复杂度吻合。

\medskip

更一般地，完全背包的时间复杂度\textbf{确实}是"物品种类数 $\times$ 背包容量"。我们来直观理解为什么：

\begin{itemize}
	\item 外层循环枚举的是"用哪种物品来更新"，共 $n$ 轮。
	\item 内层循环枚举的是"更新哪个容量的状态"，共 $W$ 步。
	\item 每一步的转移是 $O(1)$ 的（直接比较取 $\min$）。
\end{itemize}

因此总时间为 $O(nW)$。这与 0-1 背包的复杂度形式相同——区别仅在于内层循环的枚举方向（正序 vs 逆序），不影响循环次数。

如图~\ref{fig:knapsack} 所示，完全背包的 DP 表可以看作一个 $n \times W$ 的网格，每个格子恰好被访问一次。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.62, every node/.style={font=\footnotesize}]
	\def\numItems{5}
	\def\capacity{8}

	% 网格
	\foreach \i in {1,...,\numItems} {
		\foreach \j in {1,...,\capacity} {
			\fill[knapsack!8] (\j-0.45, -\i+0.45) rectangle (\j+0.45, -\i-0.45);
			\draw[knapsack!30] (\j-0.45, -\i+0.45) rectangle (\j+0.45, -\i-0.45);
		}
	}

	% 高亮当前更新行
	\foreach \j in {1,...,\capacity} {
		\fill[highlight!30] (\j-0.45, -3+0.45) rectangle (\j+0.45, -3-0.45);
		\draw[highlight!60] (\j-0.45, -3+0.45) rectangle (\j+0.45, -3-0.45);
	}

	% 列标签 (容量)
	\foreach \j in {1,...,\capacity} {
		\node[above] at (\j, 0.5) {$w\!=\!\j$};
	}

	% 行标签 (物品)
	\foreach \i in {1,...,\numItems} {
		\node[left] at (0.3, -\i) {$L\!=\!\i$};
	}

	% 轴标签
	\node[above, font=\small\bfseries] at (4.5, 1.2) {背包容量 $W$};
	\node[left, rotate=90, font=\small\bfseries] at (-0.8, -3) {物品种类 $n$};

	% 箭头标注
	\draw[-{Stealth}, highlight, line width=1.5pt] (0.55, -3) -- (8.45, -3);
	\node[right, highlight!80!black, font=\small\bfseries] at (8.6, -3) {正序扫描};

	% 总计标注
	\node[font=\bfseries] at (4.5, -6.3) {每格 $O(1)$，共 $n \times W$ 格 $\Rightarrow$ 总 $O(nW)$};
\end{tikzpicture}
\caption{%
	完全背包的 DP 表示意图。外层遍历 $n$ 种物品（行），内层正序遍历容量 $W$（列），每格恰好访问一次，总复杂度为 $O(nW)$。%
}
\label{fig:knapsack}
\end{figure}

\section{完整算法流程}

\begin{enumerate}
	\item \textbf{预处理}：对每个批次大小 $L \in [1, N]$，遍历 $M$ 种交通工具，计算 $C_L$。时间 $O(NM)$。
	\item \textbf{完全背包 DP}：以批次大小为物品、订单总数为容量，求最小代价。时间 $O(N^2)$。
	\item \textbf{输出}：$f_N - X$。
\end{enumerate}

\section{代码实现}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = (1ll << 61) - 1;

struct Solve {
	ll N, M, X;
	vector<array<ll, 2> > abls;
	vector<ll> dp;   // dp[L] = 单批送 L 个订单的最小耗时
	vector<ll> dpN;  // dpN[w] = 送前 w 个订单的最小总耗时（含统一折返）

	Solve() {
		cin >> N >> M >> X;
		abls.resize(M);
		for (int i = 0; i < M; ++i) {
			cin >> abls[i][0] >> abls[i][1];
		}
		// 预处理单批次最优耗时
		dp.resize(N + 2, INF);
		for (int L = 1; L <= N; ++L) {
			for (int i = 0; i < M; ++i) {
				auto [a, b] = abls[i];
				dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
			}
		}
		// 完全背包：外层枚举物品(批次大小)，内层正序枚举容量(订单数)
		dpN.resize(N + 2, INF);
		dpN[0] = 0;
		for (int L = 1; L <= N; ++L) {
			for (int w = L; w <= N; ++w) {
				dpN[w] = min(dpN[w], dp[L] + dpN[w - L] + X);
			}
		}
		cout << dpN[N] - X << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve solve;
	return 0;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：预处理 $C_L$ 需 $O(NM)$，完全背包 DP 需 $O(N^2)$。总计 $O(NM + N^2)$。在 $N, M \le 5000$ 的范围下，运算量约 $5 \times 10^7$，C++ 下可在百毫秒内完成。
	\item \textbf{空间复杂度}：$O(N + M)$，用于存储 $C_L$ 数组、DP 数组和交通工具属性。
\end{itemize}

\end{document}

PDF

其实我觉得 AI 说的不好，不过为了方便索引还是贴过来了

其实就是一个完全背包问题

Solve() {
    cin >> N >> M >> X;
    abls.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> abls[i][0] >> abls[i][1];
    }
    dp.resize(N + 2, INF);
    for (int L = 1; L <= N; ++L) {
        for (int i = 0; i < M; ++i) {
            auto [a,b] = abls[i];
            dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
        }
    }
    dpN.resize(N + 2, INF);
    dpN[0] = 0;
    for (int L = 1; L <= N; ++L) {
        for (int w = L; w <= N; ++w) {
            if (w - L < 0) {
                continue;
            }
            if (dp[L] + dpN[w - L] + X < dpN[w]) {
                dpN[w] = dp[L] + dpN[w - L] + X;
            }
        }
    }
    cout << dpN[N] - X << "\n";
}

AC代码

AC
https://www.luogu.com.cn/record/273605286

源代码

// teamname: Gospel_rock
/**
 * Problem: P16229 [蓝桥杯 2026 省 A] 外卖配送
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16229
 * Created: 2026-04-12 10:06:32
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N, M, X;
    vector<array<ll, 2> > abls;
    vector<ll> dp;
    vector<ll> dpN;

    Solve() {
        cin >> N >> M >> X;
        abls.resize(M);
        for (int i = 0; i < M; ++i) {
            cin >> abls[i][0] >> abls[i][1];
        }
        dp.resize(N + 2, INF);
        for (int L = 1; L <= N; ++L) {
            for (int i = 0; i < M; ++i) {
                auto [a,b] = abls[i];
                dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
            }
        }
        dpN.resize(N + 2, INF);
        dpN[0] = 0;
        for (int L = 1; L <= N; ++L) {
            for (int w = L; w <= N; ++w) {
                if (w - L < 0) {
                    continue;
                }
                if (dp[L] + dpN[w - L] + X < dpN[w]) {
                    dpN[w] = dp[L] + dpN[w - L] + X;
                }
            }
        }
        cout << dpN[N] - X << "\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve solve;
    return 0;
}

/*
AC
https://www.luogu.com.cn/record/273605286

*/

心路历程（WA，TLE，MLE……）