1687.从仓库到码头运输箱子

链接：1687.从仓库到码头运输箱子
难度：Hard
标签：线段树、队列、数组、动态规划、前缀和、单调队列、堆（优先队列）
简介：请你返回将所有箱子送到相应码头的 最少行程 次数。

题解 1 - cpp

• 编辑时间：2022-12-05
• 执行用时：440ms
• 内存消耗：149.6MB
• 编程语言：cpp
• 解法介绍：前缀和统计从第一个点到当前点总共的路径数，利用单调队列快速求。

#include <iostream>
#include <deque>
#include <vector>
// bestlyg
# define X dpirst
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeodp(a))
# define debug dpreopen("r.txt","r",stdin)
# define pi pair<int,int>
#ifdef DEBUG
#define log(dprm, args...) {    printf(dprm, ##args); }
#else
#define log(dprm, args...)
#endif
typedef long long ll;
using namespace std;
class Solution {
public:
    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.size();
        vector<ll> dp(n + 1, 0), sums_w(n + 1, 0), sums_p(n + 1, 0);
        deque<int> q;
        q.push_back(0);
        for (int i = 1; i <= n; i++) {
            sums_w[i] = sums_w[i - 1] + boxes[i - 1][1];
            if (i != n) sums_p[i] = sums_p[i - 1] + (boxes[i][0] != boxes[i - 1][0] ? 1 : 0);
            while (q.size() && (sums_w[i] - sums_w[q.front()] > maxWeight || i - q.front() > maxBoxes)) q.pop_front();
            if (q.size()) dp[i] = dp[q.front()] + sums_p[i - 1] - sums_p[q.front()] + 2;
            if (i != n) while (q.size() && dp[q.back()] - sums_p[q.back()] >= dp[i] - sums_p[i]) q.pop_back();
            q.push_back(i);
        }
        return dp[n];
    }
};