蓝桥杯:历年试题PREV-37— 分巧克力

在 1~100000 之间查找满足分巧克力要求的的最大解，线性查找用二分法。

while(left<=right)
{
    int temp=(left+right)/2;
    if(check(K,N,temp))
	left=temp+1;
    else
	right=temp-1;
}

由于不是查找指定值，因此需要错开平均值来结束程序。结束二分查找后最大值可能是两个数，left 和 left-1 。这是因为最后一次判断平均值可能是成功的，然后 left = temp + 1 后结束，这种情况最大值是 left - 1 ；同理如果最后一次判断是失败的，那么循环是因为 right=temp-1 而终止，left 就是最大值。

#include<stdio.h>
#include<stdlib.h>
#define arrmax 100000+1
int Narray[arrmax],Karray[arrmax];
int check(int key,int N,int temp)
{
	int i,sum=0;
	for(i=1;i<=N;i++)
		sum+=(Narray[i]/temp)*(Karray[i]/temp);
	if(sum>=key)
		return 1;
	return 0;
}
int main(int argc,char **argv)
{
	int N,K;
	scanf("%d%d",&N,&K);
	int i;
	for(i=1;i<=N;i++)
		scanf("%d%d",&Narray[i],&Karray[i]);
	int left=1,right=arrmax-1;
	while(left<=right)
	{
		int temp=(left+right)/2;
		if(check(K,N,temp))
			left=temp+1;
		else
			right=temp-1;
	}
	if(check(K,N,left-1))
		left--;
	printf("%d\n",left);
	return EXIT_SUCCESS;	
} 

END