wqs二分口胡

一般形态：

在 \(n\) 件物品中选出 \(m\) 件，每件物品有一个（可用数字表示的）与选择方案强相关的权值，每种选择方案也可带来（不是任何一个可选物品直接提供的）额外权值，求最终权值和的最小/最大值。额外要求：

• 令答案为关于选出物品数量 \(x\) 的函数 \(g(x)\)，则 \(y=g(x)\) 具有上凸或下凹性；
• 在选出物品数 \(x\) 不变时，对所有待选物品权值的统一同数值扰动 不会影响最优选择方案带来的额外权值。

已经尽量在抽象化了，描述得像依托答辩

​ 画出 \(y=g(x)\)，不妨设其上凸，我们求的是权值和的最大值，方便起见邻点间用线段相连：

​ 我们的目标是由 \(m\) 求 \(g(m)\)。用上第二条要求，考虑二分一个 \(k\)（为什么可以二分马上便知），把所有可选物品的权值加上 \(k\)。那么，在选出物品数 \(x\) 不变的前提下，由于选择方案的额外权值不变，新的 答案（权值最大值）关于选出物品数的函数可以表示成
​ $$f(x)=g(x)+kx$$

​ 此时我们可以用各种玄学方法（除了它的定义）求出 \(f(x)(x\in[0,n])\) 的最大值（p.s.注意与题目所述“最终权值和的最大值”区分开，那个是一个确定而难求的函数 \(g(x)\) 在 \(x=m\) 时的取值，这个是一个随着 \(k\) 变化的函数在定义域内的最大值）以及其极值点 \(x_0\)。

​ 有何用处？不急，稍作分析。考虑一条斜率确定而截距不定的直线
​ $$y=-kx+f(t)\quad (t\in[0,n])$$

​ 其中 \(k\) 就是我们二分的那个 \(k\)。由于 \(f(x)\) 在 \(x_0\) 处取得最大值，所以在 \(t=x_0\) 时这条直线最“靠上”，表达式为 \(y=-kx+f(x_0)\)，在 \(x=x_0\) 时恰有 \(y=-kx_0+f(x_0)=g(x_0)\)，\(\therefore\) 直线过 \((x_0,g(x_0))\)；即，无论 \(t\) 怎样变化，这条直线在 \(x=x_0\) 时永远在 \(y=g(x)\) 下方或与之“贴合”，它是这么动的：

​

​ 容易看出对于定下的 \(k\) 和通过 \(k\) 求出的 \(f\) 和 \(x_0\)，\(y=-kx+f(x_0)\) 与 \(y=g(x)\) 在 \((x_0,g(x_0))\) 处的“贴合”关系可以被视作相切（这一步笔者也至今没搞懂，上面的图可能有助于感性理解）。由于 \(y=g(x)\) 的上凸性，其切线斜率 \(-k\) 随 \(x\) 的增加而单调递减，二分的意义马上体现出来。对二分出的每一个 \(k\) 我们都可以求出一条斜率为 \(-k\) 的 \(y=g(x)\) 的切线以及切点，那么只需要利用单调性移动 \(k\)，使切点横坐标逼近 \(m\)，便可以通过求出的切线方程得到 \(x_0=m\) 时的切点纵坐标，继而求出 \(g(m)\)。

​ 考虑全过程需要具体题目具体分析的步骤，仅在于求 \(f(x)_{\max}(x\in[0,n])\)。\(f(x)\) 和 \(g(x)\) 相同，也表示在特定的物品权值下，最终权值和的最小/最大值；等价于，通过一个二分的过程，我们把“只能恰好选出 \(m\) 个物品”的限制给生吞了，没有该限制则整个问题好做很多。

例题

​ [国家集训队]Tree I

​ CF802O

​ 持续补充中，题目分析什么的先鸽着