OpenJudge 2774 木材加工

1.链接：

http://bailian.openjudge.cn/practice/2774/

2.题目：

总Time Limit:

1000ms

Memory Limit:

65536kB

Description

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。

木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。

Input

第一行是两个正整数N和K(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000)，N是原木的数目，K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
　

Output

输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来，输出"0"。

Sample Input

3 7
232
124
456

Sample Output

114

Source

NOIP 2004

3.思路：

利用二分查找减少计算的次数

4.代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    //freopen("C://input.txt","r",stdin);

    int i;
    
    int n,k;
    cin >> n >> k;

    int sum; //sum of stick length

    int *arr_len = new int[n];
    memset(arr_len , 0, sizeof(int) * n);

    sum = 0;
    for(i = 0; i < n; ++i)
    {
        cin >> arr_len[i];
        sum += arr_len[i];
    }

    int max_len = sum / k;
    int min_len = 1;
    int mid_len;

    int count_k;
    int max = 0;

    while(min_len <= max_len)
    {
        mid_len = (max_len + min_len) / 2;

        count_k = 0;
        for(i = 0; i < n; ++i)
        {
            count_k += (arr_len[i] / mid_len);
        }

        if(count_k >= k)
        {
            if(max < mid_len) max = mid_len;
            min_len = mid_len + 1;
        }
        else
        {
            max_len = mid_len - 1;
        }
    }

    cout << max << endl;

    delete [] arr_len;

    return 0;
}