算法笔记 P134

问题：给出N根木棒长度已知但不一定相等， 现在希望通过切割得到长度相等的K根木棒，求长度相等的K根木棒最长是多少？
如：给3根木棒，长度为10， 24， 15，要切割得到7根长度相等的木棒， 则7根木棒的长度最长为6，其组合为1*6+4*6+2*6。

暴力

#include<cstdio>

const int maxn=10010;

int main(){

    int a[maxn];

    int N, K;

    scanf("%d%d", &N, &K);

    for(int i=0; i<N; i++){

        scanf("%d", &a[i]);

    }

    int num, length=1;

    do{ 

        num=0;

        for(int i=0; i<N; i++){

            num += a[i]/length;//第i根木棒可以切割成长度为length的数目 

            printf("%d ", num);

        }

        printf("\n");

        length++;

    }while(num != K); 

    printf("%d\n", length-1);

    return 0;

}

二分

#include<cstdio>

#include<algorithm>

const int maxn=10010;

int main(){

    int a[maxn];

    int N, K;

    scanf("%d%d", &N, &K);

    for(int i=0; i<N; i++){

        scanf("%d", &a[i]);

    }

    std::sort(a, a+N);

    int left=0, right=a[N-1], mid;

    while(left+1 < right){

        int num=0;

        mid = (left + right) / 2;

        for(int i=0; i<N; i++){

            num += a[i] / mid;

        }

        if(num >= K){

            left = mid;

        }

        else{

            right = mid;

        }

    }



    printf("%d\n", left);

    return 0;

}