# 生成序列中的预算选择

**出题人解法：** 先取所有非正数，再用随机枢轴划分正数，按较小部分的和缩小搜索区间。**Codex（GPT-6）贡献：** 实现完整规模的动态存储、三路划分和安全递推，补充排序方案及证明。

## 生成与非正数

使用 64 位计算递推。因余数绝对值小于 $|D|$ ，有 $|x_i|<2\times10^9$ ，生成项可存为 32 位整数。中间乘积绝对值小于 $2\times10^{18}$ ，所有项之和绝对值小于 $4\times10^{16}$ ，64 位均足够。

将所有非正数加入选择；这只会增加数量且不会增加费用。同时从剩余预算中减去它们的和。如果剩余预算仍为负，说明连所有非正数的和都高于原预算。这是所有子集能达到的最小和，因此无可行解，按约定输出零。

否则只需考虑正数。对任意固定数量，最便宜的选择都是该数量个最小值：若选中了较大值却没选较小值，交换后不会增加费用。因此答案一定能由排序后某个前缀实现。

## 随机三路划分

在未处理正数中选一个枢轴 $v$ ，划分为小于、等于、大于 $v$ 的三段，并统计较小段之和 $s$ .

- 若 $s>L$ ，所需前缀在较小段内部，丢弃其余两段并继续。
- 若 $s\le L$ ，先全部选择较小段，扣掉费用。等于枢轴的 $c$ 项中，可选择 $\min(c,\lfloor L/v\rfloor)$ 项。
- 如果相等段没有全部选完，就已得到最大前缀。否则继续在较大段寻找。

三路划分一次性处理相同值；非正数已单独处理，所以除以 $v$ 总是合法。

## 正确性与复杂度

交换论证保证只需寻找最便宜前缀。每次分支要么把搜索限制到前缀结束所在的较小段，要么确定地消费完整较小段和可支付的相等段，所以保持答案与剩余预算的不变量。区间耗尽或无法付清相等段时，不存在可再加入的更小值，得到最大数量。

对均匀随机枢轴，选择阶段期望线性，连同生成共期望 $O(n)$ 时间、$O(n)$ 空间。最坏时间可达 $O(n^2)$ .代码采用固定伪随机种子方便复现，这不提供针对任意输入的最坏线性保证。使用完整区间的均匀分布，不把范围很小的 `rand()` 输出直接当成大区间内均匀下标。

[排序前缀方案](solution-alternative.zh.md)有确定的 $O(n\log n)$ 时间，见[程序](alternative.cpp)。它提供更直接的排序结构，但在参考环境的完整压力数据上超过本题预估时限，因此作为备用和结果核对程序；标准程序采用出题人的划分算法。

## 实现与验证

[标准程序](std.cpp)、[生成器](tests/generate.py)、[测试配方](tests/plan.json)。

参考环境中标准程序最慢中位数 0.258953 秒，峰值 81.48 MiB，校准时限 1.0 秒。每例独立运行五次。

[评测环境](../../../docs/评测环境与性能.md)与[逐次时间和哈希](../../../docs/benchmark-R31.json)。数值只适用于所记录环境，迁移评测机需重新校准。