Leetcode 1011. 在 D 天内送达包裹的能力（DAY 179）---- 二分查找学习期

曾经终败给现在 2022-09-14 02:39 21阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷超时 TLE 50/85 dp）
     *  代码实现（首刷看了点思路点拨后 二分自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷超时 TLE 50/85 dp） ##

--------------------

class Solution { 
    public:
        int shipWithinDays(vector<int>& weights, int days) { 
            vector<vector<int>> dp(weights.size(),vector<int>(weights.size(),0));
            for(int i=0;i<weights.size();++i)
            { 
                for(int j=i;j<weights.size();++j)
                { 
                    if(i == j)  dp[i][j] = weights[j];
                    else    dp[i][j] = dp[i][j-1] + weights[j];
                }
            }
    
            vector<int> now_min(weights.size(),0),pre_min(now_min),tmp_zero(pre_min);
            vector<bool> now_visit(weights.size(),false),pre_visit(now_visit),tmp_false(now_visit);
            int ret = INT_MAX;
            for(int i=0;i<days;++i)
            { 
                now_visit = tmp_false;
                now_min = tmp_zero;
                for(int start=i;start<weights.size();++start)
                { 
                    if(start && !pre_visit[start-1])  continue;
                    for(int end=start;end<weights.size();++end)
                    { 
                        now_visit[end] = true;
                        if(!start)
                        { 
                            now_min[end] = dp[start][end];
                            continue;
                        }
                        if(!now_min[end]) now_min[end] = max(pre_min[start-1],dp[start][end]);
                        else  now_min[end] = min(now_min[end],max(pre_min[start-1],dp[start][end]));
                    }
                }
                pre_visit = now_visit;
                pre_min = now_min;
                if(pre_visit.back())    ret = min(ret,pre_min.back());
            }
            
            return ret;
        }
    };

--------------------

## 代码实现（首刷看了点思路点拨后 二分自解） ##

--------------------

class Solution { 
    public:
        int shipWithinDays(vector<int>& weights, int days) { 
            int left = 0,right = 0,sum = 0;
            for(const auto& num:weights)
            { 
                left = max(left,num);
                right += num;
            }
            sum = right;
    
            while(left < right)
            { 
                int mid = (left + right)/2;
                int tmpsum = 0;
                int day = 1,pos = 0;
                while(day <= days && pos < weights.size())
                { 
                    if(tmpsum + weights[pos] > mid)
                    { 
                        tmpsum = 0;
                        ++day;
                    }
                    else
                        tmpsum += weights[pos++];
                }
                if(day > days) left = mid+1;
                else    right = mid;
            }
            return left;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b1e8256653f048d8a47e72a72149435b.png