题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

个人体感上蓝下紫。

考虑我们什么时候会算错。

按原价从大到小排序，以下认为前面代表大，后面代表小。

首先这个按性价比选，看起来其实是一种很优的贪心策略，通过手模，我们发现算错当且仅当你现在剩两块钱，有一个没选的赋值为 $2$ 的数，比接下来两个没选的赋值为 $1$ 的数更优，但性价比不如第一个没选的赋值为 $1$ 的数。设这三个数分别为 $a,b,c$，那么这三个数需要满足以下条件：

于是枚举 $a,b$，我们发现满足条件的 $c$ 是一段后缀，而 $c$ 后面的所有数都可以选或不选，假设后面长度为 $len$，贡献就是 $\sum\limits_{i=0}^{len} 2^i=2^{len+1}-1$。

再观察，枚举 $a,b$，我们发现 $c$ 取值是单调的，于是我们类似双指针那样搞一下。

接着考虑我们开局有 $m$ 元，我们要用掉剩下的 $m-2$ 元。通过观察，首先我们发现 $a$ 一定在 $b$ 前面，其次是 $a$ 前面的数定价 $1/2$ 都会被买，$a$ 和 $b$ 中间的数定价 $1$ 会被买而 $2$ 不会，我们让前面的 $1/2$ 整体减 $1$，问题变成了在中间这么多位置中选出固定个数个位置变成 $1$，预处理组合数即可。

时间复杂度 $O(n^2)$，代码等出来贴。