夏令营7.14总结

二分

lower_bound与upper_bound

用于查找在一个有序数组中的元素。lower_bound(a,b,x)返回第一个不小于x 的元素的指针或迭代器。如果不存在就返回e；upper_bound(a,b,x)是返回第一个大于x 的指针或迭代器。如不存在返回e。

lower_bound是大于等于，upper_bound是大于。

参数：初始地址，结束地址，数字返回的参数也是地址，要减去开始地址。

示例：lower_bound(a+1,a+n+1,n)-a，这样就是一个下标了。

这两个也支持cmp。原理与sort一样。sort的cmp的一个重要的注意事项：cmp(x,y)与cmp(y,x)绝对不能返回一样。

不知道为什么写着突然就这样了

运算符重载

可以在自己定义的数据结构里重载运算符。尽量不要重载int等常用类型的运算符！！！ 否则肯可能出现各种奇怪的错误，比如会把for的<也重载了。

但是如果是自己的数据结构，可以在二分时重载运算符。这样二分的判断函数更加简单。

例题

一个二分搜索的简单模板

template<typename T>
ll erfensousuo(T check,ll ok,ll ng){

	while(abs(ok-ng)>1){
		ll x=(ok+ng)/2;
		if(check(x)){
			ok=x;
		}
		else ng=x;
	}
	return ok;
}

普通二分

T1 相交的区间

给定一个区间，计算完全在这个区间左边的区间有多少个。

$x=lower_bound(a+1,a+n+1,l_i)$

通过容斥原理排除大量的解，然后把L与R拆开。

T2 超速检测

去年$\Huge CSP-S$的T2。

先算出每一辆车在那一段超速，再简单的lower_bound一下，判断区间内的第一个和最后一个测速仪。这样，就变成了昨天的区间选点问题。

保留最少的区间（每辆车的超速范围），使得每个区间（超度范围）都有点（测速仪）。

二分答案

T3 项目计划

$a_i>x$最多用$x$个人，$a_i\le x$最多用$a_i$个人。

判定性问题：$sum+=min(a_i,x)$，$if(sum>=x\times k)$

上图的意思就是说如果项目弄着弄着没人了，那么只要让另一个人来替补就可以了。

假设有x个房间。一个部门如果有大于x个人，就拉x个人，否则全部拉来。不够的，就换一个部门，按顺序放进一个房间。这样，有的人都可以用上。

T4 花束

可以做$P$个，$1\sim P$都可以。

约束条件：

• $m\times x+n\le R$
• $m+n\times y\le B$
• $0\le m$
• $0\le n$
• $n,m$为整数

在这些条件下，$m+n=K$是否成立。

把$m\times x+n\le R$写成$m(x-1)+(m+n)\le R$，所以$m\le(R-K)/(x-1)$。

同理可得$n\le (B-K)/(y-1)$。

于是，只要判断是否有$K\le\int{\frac{R-K}{x-1}}+\int{\frac{B-K}{y-1}}$。

T5 平均数和中位数

分数二分，所以这题要对精度很敏感。

这里要用double这个在printf输出时有一个注意点：double是lf，long double是Lf，是一个大写的区别。

分数在二分时，每次check就可以把答案缩小一半。多进行几次check，就可以把范围弄到很小。

T6 扫地机器人

取一个非负整数$L$，判断花$L$秒能不能清理完所有垃圾。

其中，1、2类机器人的活动范围是固定的。所以问题变成3类机器人能不能在$L$秒内清理完剩余的垃圾。

这样。我们就可以想到加一个条件：不要让两个3类机器人迎面相遇。这样会浪费3类机器人的时间。

那么继续思考，就不难想到如果在其他类机器人清理完之后，如果还有其他垃圾的话，那么左边的垃圾都是他负责。否则就一个向右走。

T7 种树

$\Huge 又是CSP真题$

代码有点长，还没搞明白，先不写