二分

参考资料

check 函数的返回值应为 $\set{0,0,\dots,0,0,1,1,\dots,1,1}$ 。

二分结束后， $l$ 为第一个 $1$ 的位置， $l-1$ 为最后一个 $0$ 的位置。

83 Bcpp
int l=x,r=y+1;
while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))r=mid;
	else l=mid+1;
}

90 Bcpp
double l=x,r=y;
while(r-l>eps)
{
	double mid=(l+r)/2;
	if(check(mid))r=mid;
	else l=mid;
}

单峰函数如果找最大值 f(m1)>f(m2)，找最小值 f(m1)<f(m2)。

103 Bcpp
double l=x,r=y;
while(r-l>eps)
{
	double m1=(l*2+r)/3,m2=(l+r*2)/3;
	if(f(m1)>f(m2))r=m2;
	else l=m1;
}

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$ ，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$ ，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

给定 $n$ 个形如 $ax^2+bx+c$ 的二次函数 $f_1(x),f_2(x),\dots,f_n(x)$ ，设 $F(x)=\max f_i(x)$ ，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

给出一个 $N$ 次函数，保证在范围 $[l, r]$ 内存在一点 $x$ ，使得 $[l, x]$ 上单调增， $[x, r]$ 上单调减。试求出 $x$ 的值。

有两个城市，中间相隔着一条笔直的河，现在要修路修桥将这两个城市联通，请找出一种方案使总的花费最小。