Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int maximizeSweetness(vector<int>& sweetness, int K) {
- int low, high, cuts, sum;
- low = INT_MAX; sum = 0;
- for(int &num: sweetness){
- sum += num;
- low = min(low, num);
- }
- high = sum/(K+1);
- while(low < high){
- int mid = (low+high+1)/2;
- sum = 0;
- cuts = 0;
- for(int &x: sweetness){
- sum += x;
- if(sum >= mid){
- sum = 0;
- cuts++;
- }
- if(cuts == K+1) break;
- }
- if(cuts > K)
- low = mid;
- else
- high = mid-1;
- }
- return low;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement