二分 \(\sf\small\color{gray}Binary\)

思想

要想区分不同，又想种类最少，“二”这个数值可谓是不二人选。
原因很简单。因为 1+1=2 。
那你是不是就可以取一个中间值，把一串数据分成两部分，然后依据这个中间值判断目标值是在左边还是右边？
二分查找就出来了。

二分查找

就是在一个 \(\sf\color{red}有序\) 的序列中，
每一次都取中间元素，
如果目标元素比中间元素小，就将范围缩小到左边的一半。
如果目标元素比中间元素大，就将范围缩小到右边的一半。

翻来覆去，最终便可以找到目标元素。
这比遍历查找快多了。
主要是利用了序列的 \(\sf\color{red}单调性\) \(\sf\small\color{gray}有序性\)。

查找

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

此题为板到不能再板的板子题。
不做解释。

二分函数

由于要找的数一定在数列中，就让它再 \(\sf 1\) 和 \(\sf N\) 之间着了。
找不到再判断。

int Find(int n)
{
	int R=N,L=1,M;
	while(L<R)
	{
		M=(L+R)>>1;
		if(n<=A[M])	R=M;
		else		L=M+1;
	}
	if(A[L]!=n)	return -1;
	return L;
}

完整代码

#include<cstdio>
int N,M,o,A[1000100];
int Find(int n)
{
	int R=N,L=1,M;
	while(L<R)
	{
		M=(L+R)>>1;
		if(n<=A[M])	R=M;
		else		L=M+1;
	}
	if(A[L]!=n)	return -1;
	return L;
}
int main() 
{
	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%d",&A[i]);
	for(int i=0;i<M;i++)
		scanf("%d",&o),
		printf("%d ",Find(o));
	return 0;
}

二分答案

如果我的答案在一个范围之间，我还去枚举吗？
可以用二分吗？
可以是可以，但你要保证答案序列的单调性。
每一次去算一下答案，与目标比较，然后二分。

[COCI 2011/2012 #5] EKO / 砍树

伐木工人 Mirko 需要砍 \(\sf M\) 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过， Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下： Mirko 设置一个高度参数 \(\sf H\)（米），伐木机升起一个巨大的锯片到高度 \(\sf H\)，并锯掉所有树比 \(\sf H\) 高的部分（当然，树木不高于 \(\sf H\) 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 \(\sf 20,15,10\) 和 \(\sf 17\)，Mirko 把锯片升到 \(15\) 米的高度，切割后树木剩下的高度将是 \(\sf 15,15,10\) 和 \(\sf 15\)，而 Mirko 将从第 \(\sf 1\) 棵树得到 \(\sf 5\) 米，从第 \(\sf 4\) 棵树得到 \(\sf 2\) 米，共得到 \(\sf 7\) 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 \(\sf H\)，使得他能得到的木材至少为 \(\sf M\) 米。换句话说，如果再升高 \(\sf 1\) 米，他将得不到 \(\sf M\) 米木材。

只需要把 if 里的东西换一换……

#include<cstdio>
#include<cmath>
int a[1000010];
int N,m;
unsigned long long cut(const int hight)
{
	long long ans=0;
	for(int i=0;i<N;i++)
			ans+=(a[i]-hight)>0?(a[i]-hight):0;
	return ans;
}
void cuttree(const int maxn)
{
	int L=0,R=maxn,M;
	int LM;
	while(L<=R)
	{
		M=(L+R)>>1;
		unsigned long long cutted=cut(M);
		if(abs(M-LM)<2&&cutted>m)
			break;
		if(cutted>m)
			L=M;
		else if(cutted<m)
			R=M;
		else
			break;
		LM=M;
	}
	printf("%d",M);
}
int main()
{
	scanf("%d%d",&N,&m);
	int maxn=0;
	for(int i=0;i<N;i++)
	{
		scanf("%d",&a[i]);
		maxn=a[i]>maxn?a[i]:maxn;
	}
	cuttree(maxn);
	return 0;
}

结语

二分就是更好的枚举。
记住他的局限：单调性

完结散花