过了 T2 不过 T1 是什么意思

yanjiadong · 2025-11-29 21:14:17 · 题解

非法情况就是你贪心地选下去，只剩下 2 块钱，碰到一个 w_i = 1 买掉了，然后只能买 a_x 最大的 w_x = 1，但是存在 w_j = 2 且 a_i \times 2 \gt a_j \gt a_i + a_x，就错掉了。

考虑把所有数按照从小到大排，若 w_i = 1 就把这个数往右边移。

考虑枚举 i, j, k 计算系数，其中 k 是最大的下标使得 a_k + a_i \lt a_j。我们希望从右往左取数后在 i' 花的钱 p = m - 2。

讨论一下点 x 要怎么取：

后两段的系数是好算的。有 j - i - 1 个数会对 p 产生 [0, 1] 的贡献，有 n - j 个数会对 p 产生 [1, 2] 的贡献，系数就是 \binom{(j - i - 1) + (n - j)}{(m - 2) - (n - j)}。

然后固定 i 枚举 j, k，j 和 k 肯定是单调的，双指针就完了，然后没了。