标签: 二分

6 篇文章

bzoj2122 工作评估
Description 题目链接:bzoj2122 利用空闲时间,BX希望外出工作,工作开始之前,公司就会给BX一个评估值 $X_0$,之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出,即 $X_i=X_{i-1}+D_i$,但是每天的评估值有一个上限,也就是说完整的评估公式应该是 $X_i=\min{X_i-1+D_i,L_i}…
LuoguP5356 [Ynoi2017] 由乃打扑克
Description 题目链接:P5356 一个长为 $n$ 的序列 $a$,需要支持 $m$ 次操作,操作有两种: 查询区间 $[l,r]$ 的第 $k$ 小值。区间 $[l,r]$ 加上 $k$。 $1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。 …
Luogu P1084 疫情控制 题解
Link Luogu Problem view Describe 有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时…
bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解
题意 在平面直角坐标系中有$n$个点,现在给你$3$个$L\times L$的正方形,问要用这$3$个正方形盖住所有点的最小的$L$。 思路 终于开始刷$bzoj$了$QwQ$... 非常明显,这道题肯定要二分,那么怎么写$check$呢? 可以考虑如果用一个非常大的正方形盖住了所有点,那么必定会有点在这个正方形的四条边上。所以有正方形必须在边上。…