P2541 [USACO16DEC] Robotic Cow Herd P 题解 / 最小扩展过程贪心学习笔记

zrl123456 · 2025-10-18 16:23:04 · 题解

:::::info[题目基本信息] 考察：Ad-hoc（省选/NOI-）。
题目简介：
给定 n 个序列，第 i 个序列为 \{a_{len_i}\}，现在在这 n 个序列各选 1 个数，问所选数字和前 k 小选法的所选数字总和是多少。
数据范围：

• 1\le n,k\le 10^5
• \forall i\in[1,n],1\le len_i\le 10
• \forall i\in[1,n],j\in[1,len_i],1\le a_{i,j}\le 10^8

时间限制：1s 至 3s。
空间限制：250MB。
::::: 首先我们可以想到通过一个 n 元组记录一个状态，使用堆可以做到 \Theta(nk\log nk)，显然过不了。我们考虑优化。
我们考虑一行一行扩展，这时容易发现若设目前处理的行为 x，则前 x-1 行的具体情况并不重要，x+1 行及以后都是 1，所以容易设三元组 (x,y,w) 表示处理到第 x 行，同时第 x 行扩展到了第 y 列，同时当前数字和为 w，容易扩展：

• 扩展到下一列（前提为 y\ne len_x），同时令 y\leftarrow y+1,w\leftarrow w-a_{x,y}+a_{x,y+1}。
• 跳到下一行（前提为 x\ne n），令 x\leftarrow x+1。

但是这样还是不行，每次扩展会直接跳到最后一行，相当于多了 \Theta(nk) 个状态，时间复杂度是 \Theta(nk\log k) 的。
所以我们考虑把跳行这一步省略掉，只在扩展后跳行，这样我们扩展时也能一步扩展，画出来就是这样的一棵递归树（为了清晰，我们以 \{len_n\}=\{3,2,3\} 为例，同时下图的三位数表示最开始的 n 元组）：
这是一棵多叉树，叉数最多能达到 \Theta(nV)（其中 V 是 \{len_n\} 的值域）级别，如果我们直接这样做能做到 \Theta(nkV\log nV)，还是很慢（怎么更慢了），继续优化。
现在我们唯一的需求就是减少叉数，我们想到可以左儿子右兄弟表示法，更改一下是这样的：

这时就有了一些状态转移方式，为了方便统一，我们把类似 311\rightarrow 121 的边变成 211\rightarrow 121，然后再次将状态转化为 (x,y,w)，容易发现有 3 种边：

然后我们就做完了这道题，但是还有若干细节。
:::::warning[细节]

1. 为了保证优先队列求第 k 小的正确性，我们要保证后面出现的值不小于前面出现的值，具体地：
   • 对于每个数列，将其从小到大排序。
   • 对于这 n 个数列，将它们按照 a_{i,2}-a_{i,1} 从小到大排序。
2. 上面的扩展方式只适用于 len_i\ne 1，对于 len_i=1，我们要手动计算答案并把它剔除。
   ::::: 时间复杂度为 \Theta(k\log k+nV)，空间复杂度为 \Theta(nV)。

code