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

Nephren_Sakura · 2025-11-29 17:54:59 · 题解

个人体感上蓝下紫。

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

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

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

• a > b+c
• 2 \times a < b

于是枚举 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)，代码等出来贴。