叮咚买菜配送

in Algorithm Pageviews

solve actually problem!

有一批蔬菜需要配送到一批社区，每个社区的家庭数用 communities 数组表示(下标表示社区编号，值表示对应社区的家庭个数，例如：communities[0] = 5表示第0个社区有5个家庭)。

现有num个外卖员为这些家庭配送蔬菜，配送方案如下：

  • 每个社区只安排一个人员进行配送。
  • 每个志愿者只能被分配一次任务，配送编号连续的若干个社区，即配送员可以配送communities[0]，communities[1]，communities[2]，communities[3]，但是不能配送communities[0]，communities[3]，communities[4]。
  • 为每个家庭配送蔬菜均需要1h
  • 配送员可以并行配送

请合理分配配送人员，保证能够在最短时间内完成配送任务，并返回所需的时间。

输入

第一行表示志愿者num，1 <= num <= 105

第二行 communities 社区集合，1 <= communities.size() <= 105

第三行 communities[i] 表示各社区的家庭数，1 <= communities[i] <= 104

输出

一个整数，完成配送任务最少时间花费

样例

输入样例1

2

3

40 10 20

输出样例1

40

说明：两个人同时去配送，一个人负责社区0的配送，需要花费40h；另一个人负责社区1、社区2的配送，需要花费30h。所以最少花费40h可完成所有配送

代码实现如下：

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int Deliver(int num, const vector<int> &communities)
    {
        int l = 0;
        int r = 1e5;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(communities, num, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
    
    bool check(const vector<int> &comm, int num, int cnt)
    {
        int res = 0;
        int t = 0;
        for (size_t i = 0; i < comm.size(); i++) {
            if (comm[i] > cnt) {
                return false;
            }
            
            if (t + comm[i] > cnt) {
                t = comm[i];
                res++;
                continue;
            }
            
            if (t + comm[i] == cnt) {
                t = 0;
                res++;
                continue;
            }
            
            if (t + comm[i] < cnt) {
                t += comm[i];
            }
        }
        
        if (t != 0) {
            res++;
        }
        
        return res <= num;
    }
};