Algorithm

LintCode/Wood Cut

Problem Summary

Given N pieces of wood with integer length L[i], cut them into equal to or more than K pieces with the same integer length. Find the maximum length of the small pieces.

Solution

This is typical problem that can be solved with binary search.

Be careful about integer overflow and use long long to calculate the sum of L[i].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    /*
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
	bool check(vector<int> &L,int len,int k) {
		int count = 0;
		for (int i=0;i<L.size();i++)
			count += L[i]/len;
		return count>=k;
	}
    int woodCut(vector<int> &L, int k) {
        long long sum = 0;
        for (int i=0;i<L.size();i++)
        	sum += L[i];
        if (sum<k)
        	return 0;
        int l = 0, r = sum/k;
        while (l<r) {
        	int mid = l + ((r - l)>>1) + 1;
        	if (check(L,mid,k))
        		l = mid;
        	else
        		r = mid-1;
        }
        return l;
    }
};