bai3captruong-leetcode.cpp

#include<vector>
#include<algorithm>

#define long long long

using namespace std;

long max(long a, long b)
{
    if (a > b)
        return a;
    return b;
}

bool check(vector<int> a, long k, long m )
{
    long cnt = 1, s = 0;
    for (auto i : a){
        if (s+i <= m)
            s +=i;
        else{
            cnt++;
            s = i;
        }
        if (cnt > k)
            return 0;
    }
    return 1;
}

class Solution {
public:
    int shipWithinDays(vector<int>& a, int k) {
        cin.tie(0)->sync_with_stdio(0);
        long n = a.size(), rig = 0, lef = 0, res = 0;
        for (auto i : a){
            rig += i;
            lef = max(lef, i);
        }

        while (lef <= rig){
        long mid = (lef+rig)/2;
        if (check(a, k, mid))
            res = mid, rig = mid-1;
        else
            lef = mid+1;
    }

        return res;
    }
};