python

9.7 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `303`. 运输小猫

一、题目描述

小 S 是农场主，他养了 M 只猫，雇了 P 位饲养员。

农场中有一条笔直的路，路边有 N 座山，从 1 到 N 编号。

第 i 座山与第 i−1 座山之间的距离为 D_i。

饲养员都住在 1 号山。

有一天，猫出去玩。

第 i 只猫去 H_i 号山玩，玩到时刻 T_i 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 1 号山走到 N 号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 1 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 1 的山，一只猫在 2 号山玩，玩到时刻 3 开始等待。

如果饲养员从 1 号山在时刻 2 或 3 出发，那么他可以接到猫，猫的等待时间为 0 或 1。

而如果他于时刻 1 出发，那么他将于时刻 2 经过 2 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式 第一行包含三个整数 N，M，P。

第二行包含 n−1 个整数，D_2,D_3,…,D_N。

接下来 M行，每行包含两个整数 H_i 和 T_i。

输出格式 输出一个整数，表示所有猫等待时间的总和的最小值。

数据范围 2≤N≤10^5,1≤M≤10^5,1≤P≤100,1≤D_i<1000,1≤H_i≤N,0≤T_i≤10^9

输入样例：

输出样例：

二、分析

题意比较复杂，首先要明白的是 一个饲养员 某时刻 出发，能够 接走哪些猫，或者说，要满足什么条件的猫才能够被 该饲养员 接走，显然只需要到达某只猫所在山的时候,猫已经玩完了就可以接走猫了。

下面来思考 某个饲养员+某只猫 的常规情况：

设饲养员出发的时间是st，某只猫 在第h_i座山上玩，并且，要玩到t_i时间，该饲养员能够接走该猫需要 出发时间 + 赶路时间 >= 此猫玩耍的结束时间

\large st + sd_{h_i} >= t_i

① sd:d的前缀和,描述每座山距离一号山的距离,此题中t_i不用做前缀和。 ② t_i<=st+sd_{h_i}，表示t_i小，从时间方向思考，就是先到这个时间点，也就是玩完时间先到达，然后小猫开始等待人来接它，后面的是饲养员的到达时间。

此时可以接走这只猫，当讨论到具体某只猫时，sd_{h_i}和t_i都是固定的，而 饲养员 的 出发时间 st 是可以变化的。st时刻出发，可以接走 剩下猫 中的满足下面式子t_i<=st + sd_{h_i}的 所有小猫。

令：\large a_i=t_i-sd_{h_i},问题变成st时刻出发，此饲养员可以接走a_i<=st的 所有小猫。

重点：将 \large a_i 自小到大 排序，方便确定饲养员在st时刻出发，能够接走 哪些小猫

注: 极限思考法：我们认为饲养员可以瞬移，不管距离有多远，都可以0秒到达。

为了满足这个要求，那么需要把与每只小猫相关的时间，都划归到每只小猫的游玩时间上。

举栗子：假设1号小猫，原游玩时长为10小时，距离1号山8个长度,那么饲养员在2点出发，可以在到达时直接接走1号小猫，可以视为小猫1的游玩时间是10-8=2,这个2,我把它重新定义为 游玩时间。

这个 游玩时间 在概念上就有了变化，在几号山就不再重要（因为消化到转换后的 游玩时间 里了）,按新产生的 游玩时间 由小到大进行排序，就是它们被接走的顺序。

继续思考，如果只有1名饲养员,那他必须在 游玩时间最长 小猫的结束后，通过 瞬移大法 完成接猫工作，这样才能保证前面的小猫也都玩完了，可以一并接走，这样的话，需要晚点出发，除最后一只小猫外，前面的小猫多等一会也是没办法的事，否则无法接走所有小猫。

如果有2个饲养员呢？情况就会好一些：1号2点出发，接走按 游玩时间 由小到大排序后的1,2,3小猫，2号饲养员3点出发，接走4,5,6小猫,这样会使小猫的整体等待时间变少。

闫式`DP`分析法

状态表示

集合 \large f[i][j]:前i个 饲养员 接走 排好序 的前j只猫的所有方案

注：此处排好序是指在 瞬移大法 的前提下，重新计算的 游玩时间 由小到大排序。

属性所有方案的 最小等待时间和

转移方程

\large f[i][j] = min(f[i-1][k] + a_j*(j-k)-(s_j-s_k))\ k \in [0,j)

注:

前i-1个饲养员已经接走了 前k只小猫>，k + 1 \sim j只小猫由 第i个饲养员 接走

\large a_j:第j只猫的 玩完时间 减去 山的距离，也就是 第i个饲养员出发的时间 此阶段，需要接走k+1 \sim j只小猫，那么第i位出发的饲养员，出发时间st=a_j。 为啥呢？因为此时接到j个小猫时，等待时间为零，如果提前出发，则到达时无法完成接j小猫的任务；如果延误出发，则会让j号小猫多等，不划算。所以，只能是在a_j这个时间出发，最合理。(贪心)

此区间[k+1\sim j],每只猫的 等待时间 分别是\large a_j - a_{k+1},a_j - a_{k+2},...,a_j-a_j \ \Rightarrow \a_j \times (j-k) - (a_{k+1} + a_{k+2} + ...+a_j) \ \Rightarrow \ a_j \times (j-k)-(s_j-s_k)

\displaystyle s_j=\sum_{u=1}^{j}a[u],s_k=\sum_{u=1}^{k}a[u],s_j-s_k=\sum_{u=k+1}^{j}a[u]

设k是使得f_{i,j}取得最小值的那个k【最佳转移点】,则\large f_{i,j} = f_{i-1,k} + a_j \times (j-k)-(s_j-s_k)

变形原则

当前选择的转移点k是变化量，将原始的k相关的式子视为 自变量(x) 式子
由k变化后影响结果的式子视为 因变量(y) 式子
自变量前面的系数，如果是常数的话，那么视为斜率

如此处理后，变形：

\large  f_{i-1,k}+s_k=a_j\times k+f_{i,j}+s_j-a_j\times j

于是我们把转移方程写成了 y=kx+b 的形式，其中：

$\large \left{\begin{array}{l} x=k & 自变量\ y=f_{i−1,k}+s_k & 因变量\ k=a_j & 常数，视为斜率\ b=f_{i,j}+s_j−a_j×j & 在斜率固定情况下y轴截距\ \end{array}\right. $

由于 x,k 都是非严格单调递增，可以用单调队列做斜率优化，时间复杂度 O(M×P)

① 首先要明确目标: 找出 min(f[i][j])，也就是在给出i名饲养员，完成接走j只小猫，需要小猫整体的等待时间最少。 ② \large k=a_j,此时j是枚举到的固定值，即斜率是固定的，不断向下凸壳逼近，试图找到与下凸壳的交点,此时产生的截距b最小 ② \large b=f_{i,j}+s_j−a_j×j,当b最小时，因为此时s_j−a_j×j是固定值，也就是f_{i,j}最小

`Code`

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 100010;
const int P = 110;
int n, m;
int p;
int q[N];

LL d[N], t[N];
LL a[N], s[N];
LL f[P][N];
int h;

int main() {
    cin >> n >> m >> p;

    for (int i = 2; i <= n; i++) cin >> d[i], d[i] += d[i - 1]; // 从2开始
    for (int i = 1; i <= m; i++) cin >> h >> t[i], a[i] = t[i] - d[h], s[i] = s[i - 1] + a[i];
    sort(a + 1, a + m + 1); // 由小到大排序,m只小猫

    // dp初始
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= p; i++) f[i][0] = 0; // 出动i个饲养员，接0只小猫，等待0。将DP TABLE第一列修改为0

    for (int i = 1; i <= p; i++) {     // 饲养员
        int hh = 0, tt = 0;            // 哨兵
        for (int j = 1; j <= m; j++) { // 遍历小猫
            // 凸包的斜率单调上升，并且，直线的斜率也是单调上升
            // 准备在下凸壳中找到第一个斜率大于k的直线，小于k的全部剔除
            while (hh < tt && (f[i - 1][q[hh + 1]] + s[q[hh + 1]] - f[i - 1][q[hh]] - s[q[hh]]) <= a[j] * (q[hh + 1] - q[hh]))
                hh++;
            // 推出的公式
            f[i][j] = f[i - 1][q[hh]] + a[j] * (j - q[hh]) - (s[j] - s[q[hh]]);
            // 维护下凸壳 [下面是 k=(y1-y2)/(x1-x)的PK，大的干掉。同时，为了避免除法，采用了十字相乘法变形]
            while (hh < tt && (f[i - 1][j] + s[j] - f[i - 1][q[tt]] - s[q[tt]]) * (q[tt] - q[tt - 1]) <= (f[i - 1][q[tt]] + s[q[tt]] - f[i - 1][q[tt - 1]] - s[q[tt - 1]]) * (j - q[tt]))
                tt--;
            // 加入
            q[++tt] = j;
        }
    }
    cout << f[p][m] << endl;
    return 0;
}

三、总结

要注意相减顺序，在去除队首<=k的点时

 while (hh < tt && (f[i - 1][q[hh + 1]] + s[q[hh + 1]] - f[i - 1][q[hh]] - s[q[hh]]) <= a[j] * (q[hh + 1] - q[hh]))
                hh++;

如果是hh+1 -> hh 就是<= ，如果是hh -> hh+1就是>= 虽然算斜率，两点谁减谁都一样，但是咱们把分母乘过去，负数不等式要变号。队尾斜率计算同理。

9.7 KiB Raw Permalink Blame History Unescape Escape

AcWing 303. 运输小猫