分巧克力c语言

分析：分巧克力，把每一种大小列举出来，在对巧克力分解，在加上所以的分解块数，在和人数比较，如果够分，就保存这一次的结果，在增大巧克力，如果不够分了，就打印上一次的结果，如果够分，就更新结果，再次增大巧克力，如果不够分就降低巧克力的大小。

1.暴力

#include <stdio.h>
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	int m,n,j,i,k,r=0;
	scanf("%d%d",&n,&k);
	int a[n],b[n];
	for(i=0;i<n;i++){
		scanf("%d%d",&a[i],&b[i]);
		r=max(r,max(a[i],b[i]));
	}
	for(i=r;i>=1;i--){//从最大到1开始列举 
		int sum=0;
		for(j=0;j<n;j++){
			sum+=(a[j]/i)*(b[j]/i);
		}
		if(sum>=k){//如果满足就输出结果 
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}

因为暴力可能会导致我们代码运行超时，所以我们可以用二分搜索

2.二分

#include <stdio.h>
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	int m,n,j=0,i,k,x,res;
	scanf("%d%d",&n,&k);
	int w[n],s[n];
	for(i=0;i<n;i++){
		scanf("%d%d",&w[i],&s[i]);
		j=max(j,max(w[i],s[i]));//找出最大边长 
	}
	i=1;//最小边长 
	while(i<=j){//二分解决 
		int mid=(i+j)/2;
		int sum=0;
		for(x=0;x<n;x++){
			sum+=(w[x]/mid)*(s[x]/mid);
		}
		if(sum<k)j=mid-1;//不够分的话就减小 
		else{
			i=mid+1;//想要增大巧克力的大小，不断尝试 
			res=mid;//保存上一次的结果，不断优化巧克力的大小，如果14行不满足了就跳出了，打印上一次的结果 
		}
	}
	printf("%d",res);
	return 0;
}