洛谷4694 [PA2013]Raper
Luogu 分析 设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。 考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。 这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。 考虑用堆解决这个问题。 维护一个小根堆，每次将 $a_i$...
Luogu 分析 设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。 考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。 这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。 考虑用堆解决这个问题。 维护一个小根堆，每次将 $a_i$...
Codeforces Luogu 分析 二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。 由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。 考虑贪心，...
Codeforces 分析 贪心地想可以知道，主席一定优先做 $b$ 最大的，如果 $b$ 相同会做 $a$ 最小的。 那么我们把所有任务排序，使得优先级越高的越靠后。 现在假设我们选了 $p$ 个任务出来，那么一定存在一条分界线，使得线前的主席都不做，线后的主席都做。 于是我们可以枚举分界线的位置，然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个，这就是这条线...
Luogu 分析 首先，如果 $a[j]=k$ ，那么 $k$ 一定在 $j$ 的前面。 考虑从 $a[j]$ 向 $j$ 连边，构成一个图。显然，如果有环的话是无解的， 那么现在就是，如果要选子节点，必须要先选父节点。$i$ 节点第 $T$ 个选出来的话，贡献是 $Tw[i]$ 。 考虑贪心。设当前权值最小的节点为 $i$。 如果 $i$ 没有父节点的话，显然当前会选 $i$ 。 如果 ...