考虑如果只有一种物品的话怎么办，把物品按照价格从小到大排序，设 \(1\) 表示选， \(0\) 表示没选，可以记 \(f(a, x, r)\) , 表示最前面是 \(a\) 个 \(1\)，剩下的第一个 \(1\) 在 \(x\), 第二个 \(1\) 在 \(r\) 。那么每次可以把 \(f(a - 1, a + 1, x)\) 和 \(f(a, x + 1, r)\) 放到堆里（如果合法的话），这样就可以求出前 \(k\) 小了。
如果有多种物品的话，考虑设 \(f_i(x)\) 表示第 \(i\) 种物品的合法的第 \(x+1\) 小值，那么现在要求 \(\sum_{i=1}^{m}f_i(x_i)\) 的第 \(k\) 小值，考虑暴力怎么做，每次可以考虑给一个 \(x_i\) 增加 \(1\) . 但是有 \(m\) 种物品，这样的话复杂度就是 \(O(mk)\) 的了。考虑优化把物品种类按照 \(f(1)-f(0)\) 排序。这样就可以变成在最后放一个 \(1\) ， 给最后一个数加一，以及如果最后一个数是 \(1\) 的话，将其往前移 \(1\) .
总结一下这个东西的核心:如果暴力给某一位加 \(1\) 的话复杂度就是 \(O(mk)\) 的。但是把转移看成一棵树，把父亲边转成兄弟边，这样复杂度就是 \(O(k)\) 的了。具体的话就是把物品种类按照 \(f(1)-f(0)\) 排序，然后考虑把 \(1\) 往 (前 / 后）移。
标签：...,排序,xm,复杂度,物品,的话,x2,考虑,x1 From： https://www.cnblogs.com/i209M/p/17210964.html