P9600

一棵树上有两个城市 $A,B$ ，令 $x$ 到 $y$ 路径上的点集合（包括端点）为 $P_{x,y}$ ，你需要对点 $i$ 分配 $c_i$ 使得 $\sum c_i\le k$ ，同时对于一个点 $x$ ，如果 $\forall i\in P_{x,A},\operatorname{dis}(i,A)\le c_i$ 则获得 $1$ 收益， $\forall i\in P_{x,B},\operatorname{dis}(i,B)\le c_i$ 则同样获得 $1$ 收益，求合法方案中收益最大的。
\item 显然第 $i$ 个点只有可能有 $3$ 种 $c_i$ ， $0,\min(\operatorname{dis}(x,A),\operatorname{dis}(x,B)),\max(\operatorname{dis}(x,A),\operatorname{dis}(x,B))$ ，下令 $\min(\operatorname{dis}(x,A),\operatorname{dis}(x,B))=a_i,\max(\operatorname{dis}(x,A),\operatorname{dis}(x,B))=b_i$ 。
先把点分成这三类点：
可以发现如果有点 $x$ 满足 $c_x=b_x$ ，则有 $\forall i\in P_{A,B},c_i\ge a_i$ ，且 $\exists i\in P_{A,B},c_i=b_i$ ，可以分类讨论 A，B，C 类点来证明。
分两种讨论，第一种是不存在 $x$ 满足 $c_x=b_x$ ，这个直接 sort 一遍优先选距离最小的即可。不需要判断是否合法，因为先选距离更远的一定不优，如上图，如果只选择了 14，改为选 12 花费的显然更少。
第二种是存在 $c_x=b_x$ ，这个就先让所有 C 类点的 $c_i$ 加到 $a_i$ ，即 $a_i\gets b_i, b_i\gets \infty$ ，然后按照 $b_i$ 排序，排序后显然可以找到一个中间点 $pos$ ，使得 $\forall i\le pos,c_i=a_i$ 或 $c_i=b_i$ ，且 $\forall i>pos,c_i=0$ 或 $c_i=a_i$ 。
这等价于证明最优方案不存在 $\nexists x,y,b_x<b_y,c_x=0,c_y=b_y$ ，显然如果存在，让 $c_x\gets b_x,c_y\gets 0$ ，此时 $x,y$ 对答案总贡献不改变，并且 $\sum c$ 减少了。
这里也不需要判断是否合法，证明跟前面类似，先选距离更远的一定不优。
先拆贡献，在 $pos$ 前面的都先对 $\sum c$ 贡献 $a_i$ ，然后前面部分就变成了 $b_i-a_i$ ，后面部分是 $a_i$ 。以下令这部分为 $s_i$
枚举 $pos$ ，二分 $mid$ ，check $\sum\limits_{s_x\le mid} s_x\le k-\sum\limits_{i\le pos} a_i$ 。
把这个离散化一下然后放到权值树状数组里，求 $pos$ 答案就像前面的二分求，复杂度 $O(n\log^2 n)$ 。

文章操作

相关推荐

评论

P9600