讨论/题目交流/leetcode官方团队赛,小张刷题计划/
leetcode官方团队赛,小张刷题计划

用的二分法,样例也都过了,为啥WA


class Solution {
public:
    int minTime(vector<int>& time, int m) {
        int n = time.size();
        if (m >= n) return 0;
        
        int l = 1, r = 10000;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (check(mid, time, m)) {
                r = mid - 1;
            } else l = mid + 1;
        }
        return l;
    }
private:
    bool check(int mid, vector<int>& time, int m) {

        int cnt = 0, sum = 0, mx = 0;
        bool first = true;
        int j = 0;
        while (j < time.size()){
            int i = j;
            sum = time[j++];
            mx = max(mx, time[j-1]);
            for (; j < time.size() && sum + time[j] <= mid; j++) {
                sum += time[j];
                mx = max(mx, time[j]);
            }
            if (j < time.size() && sum <= mid) {
                sum += time[j];
                mx = max(mx, time[j]);
                j++;
            } 
            // now sum is >= mid
            if (sum != 0) {
                sum -= mx;
                mx = 0;
            }

            // now sum is sum - mx;
            for (; j < time.size() && sum + time[j] <= mid; j++) {
                sum += time[j];
            }
            if (sum != 0 || j - 1 == i) cnt++;
        }
        return cnt <= m;
    }
};
展开讨论

嗯嗯,改了r已经过了!多谢大佬!

展开全部 3 讨论