分巧克力蓝桥杯

标题： 分巧克力

    儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
    小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。

    为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

    1. 形状是正方形，边长是整数  
    2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 
输入保证每位小朋友至少能获得一块1x1的巧克力。   

输出
输出切出的正方形巧克力最大可能的边长。

样例输入：
2 10  
6 5  
5 6  

样例输出：
2

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms


请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

对一块 Hi x Wi 的巧克力，将其分成边长为 side 的多块正方形巧克力，可以分成 ( Hi / side ) * ( Wi / side ) 块，side 的范围可以从 1 ~ min(Hi，Wi)；

对 N 块巧克力，用统一的 side 去切割它们，side 的范围从 1 至 N 块巧克力N条短边中的最长者。

现在可以用 side 从小至大去切割每一块巧克力，切割出来的数量大于等于K说明边长 side 满足分割条件；继续增大 side。

若切割出来的数量小于 K 说明边长 side 不满足要求，而且接下来更长的 side 也会不满足要求，所以最大的 side 就是上次的。

优化：切割 N 块巧克力的途中，当尚未切割完 N块巧克力时巧克力数量已经大于等于K了，此时不用再继续切割。

（可怜的是，OJ判断超时只给了75分）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    static int N;
    static int K;
    static int result;
    static int chocolates[][];

    public static void main(String[] args){
        Scanner reader=new Scanner(System.in);
        N=reader.nextInt();
        K=reader.nextInt();
        chocolates=new int[N][2];
        int maxShortSide=0;
        for(int i=0;i<N;i++){
            chocolates[i][0]=reader.nextInt();
            chocolates[i][1]=reader.nextInt();
            maxShortSide=Math.max(maxShortSide, Math.min(chocolates[i][0], chocolates[i][1]));    //N组数据最短边中的最长者
        }
//        for(int i=1;i<=maxShortSide;i++){
//            int num=0;
//            for(int j=0;j<N;j++){
//                num+=(chocolates[j][0]/i)*(chocolates[j][1]/i);
//                if(num>=K){
//                    result=i;
//                    break;
//                }
//            }
//            if(num<K){
//                break;
//            }
//        }
        for(int i=maxShortSide;i>=1;i--){
            int num=0;
            for(int j=0;j<N;j++){
                num+=(chocolates[j][0]/i)*(chocolates[j][1]/i);
                if(num>=K){
                    result=i;
                    break;
                }
            }
            if(num>=K){
                break;
            }
        }
        System.out.print(result);
    }
}

用二分法解决其实就是在 1~maxShortSide 范围内使用二分法进行查找，枚举量更小。

（可怜的是还是75分）（但是用C语言来编写同样过程的程序可以Accept）

下面是Accept程序

#include<stdio.h>
#include<math.h>

int N;
int K;
int result;

int max(int a,int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}

int min(int a,int b){
    if(a<b){
        return a;
    }else{
        return b;
    }
}

int main(){
    scanf("%d%d",&N,&K);
    int chocolates[100000][2];
    int maxShortSide;
    int i;
    for(i=0;i<N;i++){
        scanf("%d%d",&chocolates[i][0],&chocolates[i][1]);
        maxShortSide=max(maxShortSide,min(chocolates[i][0],chocolates[i][1]));
    }
    int left=1;
    int right=maxShortSide;
    while(right>=left){
        int mid=(right+left)/2;
        int num=0;
        int j;
        for(j=0;j<N;j++){
            num+=(chocolates[j][0]/mid)*(chocolates[j][1]/mid);
            if(num>=K){
                result=mid;
                left=mid+1;
                break;
            }
        }
        if(num<K){
            right=mid-1;
            continue;
        }
    }
    printf("%d",result);
    return 0;
}

分巧克力 蓝桥杯

分巧克力蓝桥杯