In a party there are n different-flavored cakes of volume V1, V2, V3 ... Vn each. Need to divide them into K people present in the
party such that
- Each member of party gets equal volume of cake (say V, which is the solution we are looking for)
- A given member should get a cake of single flavour only i.e. You cannot distribute parts of different flavored cakes to same
member.
- Minimum volume of cake gets wasted after distribution so that means a maximum distribution policy
-------------------------------------------------------------------------------------
Binary Search: We assume the volumes are int. If not, we should define an epi.
class Solution {
public:
bool isDivided(vector<int>& vi, int K, int v) {
}
int getVol(vector<int>& vi, int K) {
int sum = 0, l = 0, r = 0, maxVol = 0, mid;
sort(vi.begin(),vi.end(),greater<int>);
for (int i = 0; i < vi.size(); ++i)
sum += vi[i];
l = vi[0] / K;
r = sum / K;
while (l <= r) {
mid = (l + r) / 2;
if (isDivided(vi, K, mid)) {
if (mid > maxVol) {
maxVol = mid;
l = mid + 1;
}
else
r = mid - 1;
}
else
r = mid - 1;
}
return maxVol;
}
}
CareerCup Divide n cakes to k different people,布布扣,bubuko.com
CareerCup Divide n cakes to k different people
原文：http://blog.csdn.net/taoqick/article/details/20212403