本文共 1220 字，大约阅读时间需要 4 分钟。

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
   
    & vi, int K, int v) {       }  int getVol(vector
    
     & vi, int K) {    int sum = 0, l = 0, r = 0, maxVol = 0, mid;    sort(vi.begin(),vi.end(),greater
     
      );    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;  }}
     
    
   

转载地址：http://dwboi.baihongyu.com/