差分约束

1169.分糖果

求最小值，因此求最长路。

$dist[i]$表示第$i$个小朋友分得的糖果数

$(1)A = B \iff A \geq B, B \geq A$

$(2)A < B \iff B \geq A + 1$

$(3)A \geq B \iff A \geq B$

$(4)A > B \iff A \geq B + 1$

$(5)A \leq B \iff B \geq A$

根据相对关系无法求出最值，因此建立超级源点$X_0$，根据所有小朋友都要分到糖果这一绝对关系求解

$(6)X > 1 \iff X \geq X_0 + 1$

$(7) X_0 = 0$

按照上述关系建图

362.区间

前缀和+差分约束

$dist[i]$表示前$i$个数中选几个

$(1)s_i \ge s_{i - 1}, 1 \le i \le 5001$

$(2)s_i - s_{i-1} \le 1$（表示第$i$个数选没选）

$(3)$对于每组$a, b, c$， 有$s_b - s_{a-1} \ge c$

1170.排队布局

最远距离，求最短路

$(1)s_i \le s_{i + 1}$

$(2)s_b - s_a \le L$

$(3)s_b - s_a \ge D$

393.雇佣收银员

前缀和+差分约束

$(1)s_i \ge s_{i - 1}$

$(2)s_{i-1} \ge s_i - num[i]$

$(3)$$s_i \ge s_{i-8}+R_i,i \ge 8$

$(4)$$s_i \ge s_{i+16} - s_{24}+R_i,0 \le i \le 7$

$(5)s_{24} \ge s_0+ans,s_{24} \le s_0+ans $

答案是所有收银员的和，即$s_{24}$