python/TangDou/AcWing/ConvexHullTrick/303.md

## [$AcWing$ $303$. 运输小猫](https://www.acwing.com/problem/content/description/305/)

### 一、题目描述
小 $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$

**输入样例**：
```cpp {.line-numbers}
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
```

**输出样例**：
```cpp {.line-numbers}
3
```

### 二、分析

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

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

设饲养员出发的时间是$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$时刻出发，能够接走 **哪些小猫**

><font color='red' size=4><b>注:</b></font>
 极限思考法：我们认为饲养员可以瞬移，不管距离有多远，都可以$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$
```cpp {.line-numbers}
#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$的点时
```cpp {.line-numbers}
 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$就是$>=$ 虽然算斜率，两点谁减谁都一样，但是咱们把分母乘过去，负数不等式要变号。队尾斜率计算同理。