蓝桥杯2017年第八届真题-分巧克力 （C++代码）

解题思路:
【思路一】枚举每个小巧克力的边长，并把该边长下共有几个小巧克力映射到该边长，用数组实现。然后二分查找小巧克力的个数，再根据映射得到边长。    ！超时！枚举每个边长并计算该边长下小巧克力的数目，数据太大了。男票提供了思路二！

【思路二】二分查找符合条件的边长，条件用ok()函数来判断。

注意事项:

参考代码:

【思路一代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e+5 + 10;

//int Bc2num[6] = {5,4,3,2,1,0};
int Bc2num[maxn],H[maxn],W[maxn];
int n, k, Max = -1;

int lower_bound(int left, int right, int x){
int mid;
while(left < right){
mid = (left + right) / 2;
if(Bc2num[mid] <= x){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}

int main(void){
scanf("%d%d",&n,&k);
memset(Bc2num,0,sizeof(Bc2num));
memset(H,0,sizeof(H));
memset(W,0,sizeof(W));
for(int i = 1; i <= n; i++){
scanf("%d%d", &H[i], &W[i]);
if(Max < max(H[i], W[i])){
Max = max(H[i], W[i]);
}
}

for(int i = 1; i <= Max; i++){
int num = 0;
for(int j = 1; j <= n; j++){
num += (H[j]/i) * (W[j]/i);
}
Bc2num[i] = num;
} 

//	for(int i = 0; i <= 5; i++){
//
//	printf("%d ",Bc2num[i]);
//	}

int ans = lower_bound(0, Max, k);
printf("%d",ans-1);
//	int ans = lower_bound(0, 5, 1);
//	printf("%d",ans);
return 0;
}

【思路二代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e+5 + 10;

int H[maxn],W[maxn];
int n, k, Max = -1;
int l = 1,m,r;
int ans = 1;

bool ok(int m){
int sum = 0;
for(int i = 1; i <= n; i++){
sum += (H[i]/m) * (W[i]/m);
} 
if(sum >= k) return true;
else return false;

}

int main(void){
scanf("%d%d",&n,&k);
memset(H,0,sizeof(H));
memset(W,0,sizeof(W));
for(int i = 1; i <= n; i++){
scanf("%d%d", &H[i], &W[i]);
if(Max < max(H[i], W[i])){
Max = max(H[i], W[i]);
}
}

r = Max;
while(l <= r){
m = (l + r) / 2;
if(ok(m)){
ans = m;
l = m + 1;
}else{
r = m - 1;
}
}
printf("%d",ans);
return 0;
}

【官答】

#include<stdio.h>
#define N 100000
bool ok(int m);
int a,b;
int H[N],W[N];
int main()
{
int c,l=1,max=0,r,ans=1;
long long m;
scanf("%d %d",&a,&b);
for(c=0;c<a;c++)
{
scanf("%d %d",&W[c],&H[c]);
if(max<=W[c])
   max=W[c];
if(max<=H[c])
  max=H[c];  
}
r=max;
while(l<=r)
{ 
int m=(l+r)/2;
if(ok(m))ans=m,l=m+1;
else r=m-1;
}
printf("%d",ans);
return 0;
}
bool ok(int m) 
{
  long long c = 0;
  for(int i = 0; i < a; i++) 
  {
    c+=(long long)(H[i]/m)*(W[i]/m);
  }
  if(c>=b) return true;
  return false;
}