A. 大副
令 \(m\) 的最高一位 \(1\) 在 \(k\) 上。
构造 \(\lfloor n/2\rfloor\) 个 \(2^k\)，\(n-\lfloor n/2 \rfloor\) 个 \(2^k-1\)，即可达到答案上界 \((2^{k+1}-1) \times \lfloor n/2\rfloor \times (n-\lfloor n/2 \rfloor)\)。
B. 机械师
首先 小甜水糖水不等式。多人同时破译多台机器是不优的。也即每个时刻都是所有人同时破译一台机器。
我们称最终变成机械玩偶的密码机为 A，只是破译的密码机为 B。
observasion 1：
一定先加工完所有 B 密码机后，再加工所有 A 密码机。
加工 B 密码机时一定按照 \(b_i\) 的递增顺序加工。
不妨枚举最终 B 密码机的数量 \(x\)。这样我们就能得到加工 A 时的速度。
将所有密码机按照 \(b_i\) 递增排序。那么最终的 B 密码机一定是按照编号顺序依次加工的。
此时做 DP。设 \(f(i, j, k)\) 表示前 \(i\) 个密码机中，有 \(j\) 个加工成 A，\(k\) 个加工成 B，最小花费时间是多少。
转移：
\[f(i, j, k) = \min\begin{cases}f(i-1,j,k) & \\ f(i-1,j-1,k)+\frac{a_i}x & j \ne 0 \\ f(i-1,j,k-1)+\frac{b_i}k & k \ne 0 \end{cases} \]答案为 \(f(n, m-x,x)\)。其中 \(m\) 是原题给定的 \(k\)。
总复杂度 \(\mathcal O(n^4)\)。考虑优化。
observasion 2：
每个 B 密码机前面的所有密码机一定都被加工（成 A 或 B）。
这是因为如果前面存在一个不被加工的，那么将这个加工成 B，原来的不加工，对后续的影响不变且效益更优（越往前 \(b\) 越小）。
所以状态里 \(j=i-k\) 是定值。状态数变成了 \(\mathcal O(n^2)\)。
考虑如何计算答案。不妨枚举最后一个 B 机器的位置 \(i\)。那么 \([1,i]\) 中一定有 \(i-x\) 个 A 和 \(x\) 个 B。A 的数量可能不够，还需要在 \([i+1,n]\) 中选择 \((m-x)-(i-x)=m-i\) 个。而这 \(m-i\) 个一定是 \(a\) 最小的。nth_element 即可。
总复杂度 \(\mathcal O(n^3)\)。
标签：密码机,lfloor,加工,11.6,rfloor,一定,mathcal,模拟 From： https://www.cnblogs.com/2huk/p/18530272