外部链接公众号无效，点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

差分约束问题

差分约束是一种特殊的N元一次不等式组。包含N个变量 ，以及M个约束条件，其中每个约束条件有两个变量做差构成，形如： ，我们要做的就是求出一组 的值，使得M个约束条件全部满足。

例如：

一组可行的解是：

求解差分约束

模型分析

考虑一下差分约束的表达形式： ，我们如果变形成 ，就可以发现和图论问题求最短路时候的三角不等式非常相似。

回顾一下求最短路的更新规则。假如有一条边，由点i -> j，边的权重是c，由dist数组表示最短路径，那么更新规则是：

if (dist[j] > dist[i] + c) 
    dist[j] = dist[i] + c

所以，根据更新规则，当我们求完整个最短路的时候，公式dist[j] <= dist[i] + c对于「所有的边都一定成立」，因为不成立的话就会把右边的值更新给左边。

由此，我们就可以把差分约束问题转换为最短路问题，对于每个差分约束中的不等式 ，我们都可以转换成「由 点j 到 点i 连接一条边，边权是C」。

使用这种转换规则，我们就把整个不等式方程组转换成了一个图，然后对整个图做一个单源最短路算法，如果图中不存在环（方程组无解），那么我们就能找到一组解。

这里还有一点需要注意，后文，我们所有说的「不等式」，均是已经「求完最短路或者最长路之后」，所满足的三角不等式。尤其是在后文最大值最小值部分，一定要牢记这一点，否则容易懵圈。

源点选择

根据我们以前的内容，最短路算法都是需要一个源点的，那么，从差分约束转换的图，应该如何选择源点呢？

其实认真考虑一下就可以发现，只要「源点最终可以到达所有点」就可以了，这样我们做完最短路算法，才能保证更新出所有的最短路径，而没有遗漏。

图中存在负环会如何？

现在，我们考虑一下转换后图中存在负环会是什么情况。

根据图中推导的最终结果，我们可以得到结论：「如果图中存在负环，则说明不等式组矛盾，也就是不等式组无解」。

求解步骤

1. 将所有不等式 ，转换成「由 点j 到 点i 连接一条边，边权是C」。
2. 找到一个超级源点，使得该源点最终可以到达所有边。
3. 从这个超级源点，做一遍最短路算法。
4. 最终我们会得到两种结果：

   1. 图中存在负环，不等式无解；
   2. 图中不存在负环，最短距离数组dist[i]，即是不等式组的一组可行解。
5. 与最短路相对应的，也可以通过最长路求出一组可行解，最长路时，则通过正环判断是否有解。

求可行解的最大值或者最小值

前提条件

如果要求最大值或者最小值，则「一定有一个不等式是绝对条件」，比如： 或者 等，如果没有这种「绝对条件」，则每个变量 都是参照其他变量，那么就没有绝对的最大值或者最小值。

绝对条件如何转换成图中的路径

假设，当前的不等式是 ，使用超级源点的思路。我们可以虚拟出一个超级源点0，然后从0到点i连接一条边，边权为c。

求解步骤

1. 对于每个 ，我们都找到所有由它开始组成的不等式链。

   「不等式链」：对于任意 ，我们从 开始寻找不等式关系。

   比如有以下不等式关系： ， ， ，则我们沿着 出发，就能找到一条不等式链： 。

   需要注意的是，根据我们的前提条件，求最值一定会有「绝对条件」，使得我们最后可以找到一个常数来做参照。

   那么,对于任意 形成的不等式链，最后一定可以走到一个只包含常数的式子（即，例子中的 ），这个常数式子就对应了图中的一条路径（即，例子中 ）。

2. 对于 当我们找到它的所有不等式链的解之后，我们可能会得到这样的方程组：

3. 假如，我们求的是 的最大值，那么显然，对于以上不等式组，我们要取 才能使整个不等式组成立。所以我们得到最终的结论：「想求 的最大值，那么就要使用最短路，也就是找到所有由 开头的路径中，权重最小的路径」。

4. 与3中结论相对应的，我们也能用相同的方式推导出求最小值的结论：「想求 的最小值，那么就要使用最长路，也就是找到所有由 开头的路径中，权重最大的路径」，可以将2中的方程组中所有 “ ” 都翻转成 “ ”，那么最后要让方程组成立，就必须取最大值5。

AcWing 1169. 糖果

幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

「输入格式」
输入的第一行是两个整数 N,K。

接下来 K 行，表示分配糖果时需要满足的关系，每行 3 个数字 X,A,B。

如果 X=1．表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。
如果 X=2，表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
如果 X=3，表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。
如果 X=4，表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
如果 X=5，表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。

小朋友编号从 1 到 N。

「输出格式」
输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。

「数据范围」

1≤N<105,
1≤K≤105,
1≤X≤5,
1≤A,B≤N,
输入数据完全随机。

「输入样例」

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

「输出样例」

11

题目描述

给幼儿园的N个小朋友分糖果，「要求每个小朋友都能分到糖果」，其中，有的小朋友还提出了一些要求，而我们的目标是在满足小朋友要求的情况下，给出老师「至少」需要准备多少个糖果。

题目分析

根据给出的关系，我们可以把这些关系用不等式表达出来（本题要求的是「至少」，也就是「最短路（最小值）」，所以我们需要使用「最长路（最大值）算法」，因此符号用“ ”）：

1. 如果x=1，则A=B，那么有A>=B，B>=A；
2. 如果x=2，则A<B，那么有B>=A+1；
3. 如果x=3，则A>=B，那么有A>=B；
4. 如果x=4，则A>B，那么有A>=B+1；
5. 如果x=5，则A<=B，那么有B>=A；

如此，按照上述规则，我们就可以把不等式建立成图。

不过还需要考虑的一个问题是，我们在上面已经讲了求最值，必须有「绝对条件」，那么本题的绝对条件在哪呢？

其实就是题目中给出的条件“「每个小朋友都能分到糖果」”，所以说，每个小朋友分到的糖果数量x至少要有一个，也就是x>=1。

然后，根据上面所讲，我们建立一个超级源点 ，我们让 ，就可以把每一个x都转换成 ，也就是让超级源点连接到所有其他的点，而连接所有点，也就意味着「从超级源点可以到达所有边」（注意这个理论反过来不成立，可以到达任意一个边，不一定能到达任意一点，因为可能有孤立的点）。

如此，我们就把题目中的不等式转换成了图，然后只要「从超级源点做一遍最长路算法」就可以了。

Code

#include <iostream>
#include <cstring>

using namespace std;

// 注意边数M 最坏全是x=1的话 需要建两条边 
// 并且超级源点到所有点都连一条边 总共是3倍的边数
const int N = 100010, M = 300010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
long long dist[N];
int cnt[N], q[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa() {
    memset(dist, -0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 1;
    st[0] = true;
    dist[0] = 0;
    q[0] = 0;
    while (hh != tt) {
        // 因为求负环超时 所以把队列换成栈
        // 我也不知道为什么 这样可以优化
        // 但是Y总说 可以在负环超时的情况下用
        // 其他情况不可用 正常情况用可能会降低速度
        // int t = q[hh ++ ];
        // if (hh == N) hh = 0;
        int t = q[-- tt];
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return false;
                if (!st[j]) {
                    // q[tt ++ ] = j;
                    // if (tt == N) tt = 0;
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int x, a, b;
        cin >> x >> a >> b;
        if (x == 1) add(a, b, 0), add(b, a, 0);
        if (x == 2) add(a, b, 1);
        if (x == 3) add(b, a, 0);
        if (x == 4) add(b, a, 1);
        if (x == 5) add(a, b, 0);
    }
    // 虚拟源点
    for (int i = 1; i <= n; i ++ ) add(0, i, 1);
    if (!spfa()) puts("-1");
    else {
        long long res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}

AcWing 362. 区间

给定 n 个区间 [ai,bi] 和 n 个整数 ci。

你需要构造一个整数集合 Z，使得 ∀i∈[1,n]，Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。

求这样的整数集合 Z 最少包含多少个数。

「输入格式」
第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,ci。

「输出格式」
输出一个整数表示结果。

「数据范围」

1≤n≤50000,
0≤ai,bi≤50000,
0≤ci≤bi−ai+1

「输入样例」

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

「输出样例」

6

题目描述

本题的题面比较难懂，其实翻译过来就是给出n个区间[ai, bi]，对应n个ci，要求我们「构造一个整数集合，集合中的每个区间[ai, bi]必须有至少ci个数，问题是整个集合中至少有多少个数」。

而根据题目的范围0≤ai,bi≤50000，我们知道可供选择的区间就是0~50000。

题目分析

本题可以使用类似前缀和的思路来考虑，假设，我们「定义s[k]表示0~k之间最少需要选出多少个整数」。

根据我们文章开头的分析，求“最少”应该使用最长路，因此，我们要把找到的不等式都变成>=。

那么，根据s[k]的定义，我们就能推出来第一个不等式：s[i] >= s[i-1]，所表示的含义是「在0~k之间选出来的整数数量 一定 不少于0~k-1之间 选出来的整数数量」。

再考虑，我们对于给定范围内的每个整数只有两种情况一种是不选，另一种是选，如果「选就是集合内整数数量+1」，不选无影响。那么根据s[k]的含义，我们就能推出来另一个不等式：s[k]-s[k-1]<=1。表示的含义是0~k和0~k-1之间可选择的元素数量只相差一个元素，也就是k，那么该不等式的含义就是，选则k就是1，不选择k就是0，也就是<=1。转换成>=就是：s[k-1]>=s[k]-1。

最后一个不等式比较明显，既，题目中给出的条件「区间[ai,bi]之间必须选择至少ci个数」，所以有不等式s[b]-s[a-1]>=c（注意区间两端均是闭区间，必须选择a-1，才能让a被可能选择）。

那按照这种方式是否「存在一个点可以到达所有的边呢」？我们注意观察第一个不等式s[i] >= s[i-1]，「转换成图就是i-1 -> i 连接一条权重为0的边」，因此「一定会有一条边从0一直连接到最后一个点」。

另外，还有一点需要注意的是，前缀和思路中，我们的第一个元素通常是0，那为了让s[0]=0，我们把所有点，也就是「所有a和b的值均后移一位」，把数据范围变成1~50001，因为我们求的是个数，所以这样做不会影响最后结果。

Code

#include <iostream>
#include <cstring>

using namespace std;

// 边的数量为三个不等式各会连出5w条边。
const int N = 500010, M = 150010;
int n;
int dist[N], q[N];
bool st[N];
int h[N], w[M], e[M], ne[M], idx;

void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa() {
    memset(dist, -0x3f, sizeof dist);
    int hh = 0, tt = 1;
    q[0] = 0; // 0号点入队
    // 从0个整数中做选择  那么选的数量也是0
    dist[0] = 0;
    st[0] = true;
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1;i <= 50001; i ++ ) {
        add(i - 1, i, 0); // 不等式1
        add(i, i - 1, -1); // 不等式2
    }
    while (n -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式3
        a ++, b ++ ;
        add(a - 1, b, c);
    }
    spfa();
    printf("%d\n", dist[50001]);
    return 0;
}

AcWing 1170. 排队布局

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。

农夫约翰有 N 头奶牛，编号从 1 到 N，沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。

因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 L。

另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D。

给出 ML 条关于两头奶牛间有好感的描述，再给出 MD 条关于两头奶牛间存有反感的描述。

你的工作是：如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。

「输入格式」
第一行包含三个整数 N,ML,MD。

接下来 ML 行，每行包含三个正整数 A,B,L，表示奶牛 A 和奶牛 B 至多相隔 L 的距离。

再接下来 MD 行，每行包含三个正整数 A,B,D，表示奶牛 A 和奶牛 B 至少相隔 D 的距离。

「输出格式」
输出一个整数，如果不存在满足要求的方案，输出-1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；否则，输出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。

「数据范围」

2≤N≤1000,
1≤ML,MD≤104,
1≤L,D≤106

「输入样例」

4 2 1
1 3 10
2 4 20
2 3 3

「输出样例」

27

题目描述

有一些奶牛，「沿着一条直线」排队等待喂食，他们的排队顺序就是编号，多个奶牛可能处于相同的位置。有一些奶牛有好感，这些奶牛之间的距离不能超过L，有一些奶牛互相讨厌，这些奶牛的距离不能小于D。

问题共有三问：

1. 不存在满足这些情况的方案，输出-1；
2. 如果1号牛和N号牛的距离可以无限大，输出-2；
3. 否则，输出满足所有要求情况下，1号奶牛和N号奶牛的最大距离；

题目分析

建立模型

对比上一个题目，本题的差分约束特征还是比较明显的，题面中就给出了两个明显的约束：

1. 通过题面“友好的奶牛距离不超过L”，可以得到不等式：Xb-Xa<=L；
2. 通过题面“反感的奶牛距离不小于D”，可以得到不等式：Xb-Xa>=D；

另外，本题其实还有一个不明显的约束条件，根据题面“奶牛们沿着一条直线等待喂食”，在直线中，从第1号点到N号点距离一定是逐渐递增的，所以还有一个不等式是： （注意，可以取到等号是因因为题目中说明，可能有多个奶牛在一个点）。

而本题因为是要求最大距离，所以应该使用最短路，那么，我们要把不等式符号统一成<= 。那么统一后，我们就能得到三个不等式：

1. ；
2. ；
3. ；

然后，我们又发现本题是没有明显的给出一个绝对条件用来求最大值。但是注意，所有奶牛是在一条数轴上来计算距离的，所以，我们可以让 「所有的奶牛都在数轴中0的左面」，来给出绝对条件，即，初始化每个奶牛：Xi<=0，那么该条件在图中相应的含义就是「创建一个超级源点0，从0点到所有的点连接了一条长度为0的边」。

问题一

回头看问题，在「第一问中，我们需要判断是否有解，那么根据分析出的差分约束模型，判断图中是否存在负环就可以」。

问题二

1号点和N号点间的距离是否可以无限大？

该问题中，求的是N号点相对于1号点来说的距离，也就是相对距离，这个距离要用xn-x1来求出，那么我们可以把1号点固定在特殊点0处（也就是x1=0），那么求这俩点的距离就是xn-0=xn，我们就只需要判断xn是否可以无限大就行了，就相当于从1号点求到N号点的最短路径。

问题三

根据查分约束模型，求一遍「不等式组 转换成的图 中的最短路 就行了」。

Code

实现上，有几个点需要注意：

1. 奶牛的下标是从1开始的，一直到n；
2. 超级源点可以不用建出来，只要在spfa的时候把所有点都入队，距离设置成0就行了。

#include <iostream>
#include <cstring>

using namespace std;

// 边的范围是 不等式1 边数量<=1000 不等式2、3边各10000条
const int N = 1010, M = 30010, INF = 0x3f3f3f3f;
int dist[N], cnt[N], q[N];
bool st[N];
int h[N], w[M], e[M], ne[M], idx;
int n, m1, m2;

void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    int hh = 0, tt = 0;
    for (int i = 1; i <= s; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
        dist[i] = 0;
    }
    while (hh != tt) {
        int t = q[hh ++ ];
        st[t] = false;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m1 >> m2;
    memset(h, -1, sizeof h);
    // 不等式1
    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while (m1 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式2 数据里有些a比b还大 （不知道是不是问题数据
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (m2 -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 不等式3
        if (a > b) swap(a, b);
        add(b, a, -c);
    }
    if (spfa(n)) puts("-1");
    else {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }
    return 0;
}

AcWing 393. 雇佣收银员

一家超市要每天 24 小时营业，为了满足营业需求，需要雇佣一大批收银员。

已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。

经理为你提供了一个各个时间段收银员最小需求数量的清单 R(0),R(1),R(2),…,R(23)。

R(0) 表示午夜 00:00 到凌晨 01:00 的最小需求数量，R(1) 表示凌晨 01:00 到凌晨 02:00 的最小需求数量，以此类推。

一共有 N 个合格的申请人申请岗位，第 i 个申请人可以从 ti 时刻开始连续工作 8 小时。

收银员之间不存在替换，一定会完整地工作 8 小时，收银台的数量一定足够。

现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。

「输入格式」 第一行包含一个不超过 20 的整数，表示测试数据的组数。

对于每组测试数据，第一行包含 24 个整数，分别表示 R(0),R(1),R(2),…,R(23)。

第二行包含整数 N。

接下来 N 行，每行包含一个整数 ti。

「输出格式」 每组数据输出一个结果，每个结果占一行。

如果没有满足需求的安排，输出 No Solution。

「数据范围」

0≤R(0)≤1000,
0≤N≤1000,
0≤ti≤23

「输入样例」

1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
5
0
23
22
1
10

「输出样例」

1

题目描述

一天24小时，有一个超市，给定这个超市每个小时所需要的收银员数量，给出N个可以用的申请人，每个申请人可以从第i个时刻连续工作8小时，问「最少需要」多少个收银员能满足全部时刻所需要的收银员数量。

题目分析

本题的题面还是比较清晰的，最后问题是问的“最少”，所以本题应该是「求最长路」。

然后根据题目要求“每个时刻都要满足最小数量的收银员”，所以我们「假设nums[24]为每个时刻需要的收银员数量，x[]为每个时刻 需要来的 最少收银员」，那么则一定有一个基本的不等式：0<=x[i]<=nums[i]，表示的含义是「在t[i]时刻存在的收银员数量在区间 0~nums[i]。」

另外，我们还要计算一个「每个时刻i 存在多少收银员」，可以用「前面7个时刻 来的收银员加上当前时刻来的收银员」，就是时刻i存在收银员，如果时刻i存在的收银员满足条件，它就必须大于等于R[i]，公式为：x[i-7]+x[i-6]+...+x[i]>=R[i]。

但是我们发现这个公式和差分约束需要的标准不等式有所区别，它是连续的加法，所以，比较明显的处理连续加法的方式就是使用「前缀和」。

想使用前缀和就需要把第0位空出来，所以我们让nums[]和x[]的下标均从1开始，把S[]记作「前缀和数组」。那么就有公式：s[i]=x[1]+x[2]+...+x[i]，然后我们用前缀和数组来描述前两个公式：

1. 0<=x[i]<=nums[i] => 0<=s[i]-s[i-1]<=nums[i]。
2. 而对于后面的公式，由于是1~24是循环的，所以我们要分步来看，第一部分i>=8就比较简单，直接用前缀和公式：s[i]-s[i-8]>=R[i]；第二部分0<i<=7，我们分两段来看，第一段是s[24]-s[i+16]也就是i较大的那段，第二段则是i较小那段s[i]，两段加起来就是s[i]+s[24]-s[i+16]>=R[i]。

按照求最长路的思路，把上面的几个公式整理成“>=”的：

1. 0<=s[i]-s[i-1]<=nums[i] => s[i]>=s[i-1]+0，s[i-1]>=s[i]-nums[i]；
2. 当i>=8时，s[i]-s[i-8]>=R[i] => s[i]>=s[i-8]+R[i]；
3. 当i<i<=7时，s[i]>=s[i+16]-s[24]+R[i]；

整理之后，我们发现最后一个公式还是不能满足差分约束的不等式模型，所以，我们变通一下，把s[24]不当做变量，而是当成一个常量，我们枚举所有s[24]的值，根据数据范围，最多只有1000个人，所以完全可以进行枚举。

根据本题的最终问题：「最少需要多少个收银员满足每个时刻的需求」，也就是说「问题其实就是s[24]最小是多少」，因为s[24]本身就是所有收银员数量的和。

所以，我们就可以在数据范围0~1000之间，枚举出最小的s[24]的值，使得题目满足要求即可，因此本题就具有「二段性」，可以使用「二分法」来快速找到满足要求的值。

Code

(这道题，真的可能第二天就写不出来了。)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

// 24个点，3倍的边
const int N = 30, M = 100;
int n;
int h[N], w[M], e[M], ne[M], idx;
int r[N], num[N];
int dist[N], cnt[N], q[N];
bool st[N];

void add(int a, int b, int c) {
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 建图 每个s24都要重新建图
void build(int s24) {
    memset(h, -1, sizeof h);
    idx = 0;
    for (int i = 1; i <= 24; i++ ) {
        add(i - 1, i, 0);
        add(i, i - 1, -num[i]);
    }
    for (int i = 8; i <= 24; i ++) add(i - 8, i, r[i]);
    for (int i = 1; i <= 7; i ++ ) add(i + 16, i, r[i] - s24);
    // 固定24为常量 就是让 s24 >= 0 + c, s24 <= 0 + c;
    add(0, 24, s24), add(24, 0, -s24);
}

bool spfa(int s24) {
    build(s24);
    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    q[0] = 0; // 超级源点 0可达其他所有边
    st[0] = true;
    int hh = 0, tt = 1;
    while (hh != tt) {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 25) return false;
                if (!st[j]) {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    // 本题有多组数据 别忘记初始化
    while (T -- ) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= 24; i ++ ) cin >> r[i];
        cin >> n;
        memset(num, 0, sizeof num); // 多组数据 别忘记清空num
        for (int i = 0; i < n; i ++ ) {
            int t;
            cin >> t;
            num[t + 1] ++ ; // 前缀和
        }
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if(spfa(mid)) r = mid;
            else l = mid + 1;
        }
        if(spfa(r)) printf("%d\n", r);
        else puts("No Solution");
    }
    return 0;
}

「END」