题解：雇佣收银员问题

一、题目背景

一家超市需24小时营业，不同时间段对收银员数量需求不同，经理提供了每个小时的收银员最小需求数量清单 (R(0), R(1), \cdots, R(23)) 。同时有 (N) 个合格申请人，每人可从 (t_i) 时刻开始连续工作8小时。目标是计算出满足营业需求的最少收银员雇佣数量。

二、解题思路

本题通过构建差分约束系统，利用二分答案和SPFA算法求解。将每个小时看作图中的一个节点，根据收银员的工作时间和各时段需求构建有向边。通过二分猜测雇佣收银员的数量 (c)，并利用SPFA算法判断在该数量下是否存在满足条件的方案。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、每个小时的需求数组 r[N]、每个小时可开始工作的人数数组 num[N]、距离数组 dist[N]、队列数组 q[N]、记录每个节点入队次数的数组 cnt[N] 以及节点是否在队列中的标记数组 st[N]。
2. 编写添加边的函数，用于构建邻接表。
3. 实现 build 函数，根据猜测的雇佣人数 c 构建图的边：
- 添加节点 0 与 24 之间的边，表示一天的循环，边权分别为 c 和 -c。
- 处理跨天工作的情况，对于 (1 \leq i \leq 7)，添加从 (i + 16) 到 (i) 的边，边权为 (r[i] - c)。
- 对于 (8 \leq i \leq 24)，添加从 (i - 8) 到 (i) 的边，边权为 (r[i])，表示从开始工作8小时前到当前小时的需求关系。
- 添加相邻小时之间的边，从 (i) 到 (i - 1) 的边权为 (-num[i])（表示当前小时可开始工作的人数对前一小时的影响），从 (i - 1) 到 (i) 的边权为 (0)（表示人数不会减少）。
4. 实现SPFA算法函数 spfa，通过不断更新节点距离，判断图中是否存在负权回路（即是否存在满足条件的方案）。
5. 在 main 函数中：
- 读取测试用例数量 T。
- 对于每个测试用例：
- 读取每个小时的收银员需求数量到 r 数组。
- 读取申请人数量 n，并统计每个小时可开始工作的人数到 num 数组。
- 从 (0) 到 (1000) 枚举雇佣人数 i，调用 spfa 函数判断该人数下是否存在可行方案。
- 若存在可行方案，输出该人数并标记成功；若所有人数都不可行，输出 No Solution。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

const int N = 30, M = 100, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int r[N], num[N];
int dist[N];
int q[N], cnt[N];
bool st[N];

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 30, M = 100, INF = 0x3f3f3f3f;：定义节点的最大数量、边的最大数量以及表示无穷大的常量。
3. 变量定义：
   • int n;：表示申请人数量。
   • int h[N], e[M], w[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，w[M] 存储边权，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int r[N], num[N];：r[N] 存储每个小时的收银员需求数量，num[N] 存储每个小时可开始工作的人数。
   • int dist[N];：记录从源点到每个节点的距离。
   • int q[N], cnt[N];：q[N] 是队列数组，用于SPFA算法；cnt[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 ++ ;
}

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点，c 为边权。通过更新邻接表数组，将边的信息存储起来。

（三）构建图函数

void build(int c)
{
    memset(h, -1, sizeof h);
    idx = 0;
    add(0, 24, c), add(24, 0, -c);
    for (int i = 1; i <= 7; i ++ ) add(i + 16, i, r[i] - c);
    for (int i = 8; i <= 24; i ++ ) add(i - 8, i, r[i]);
    for (int i = 1; i <= 24; i ++ )
    {
        add(i, i - 1, -num[i]);
        add(i - 1, i, 0);
    }
}

1. 初始化邻接表，将头指针数组 h 初始化为 (-1)，边编号 idx 设为 (0)。
2. 添加节点 0 与 24 之间的边，边权分别为 c 和 -c，表示一天的循环和雇佣人数的限制。
3. 处理跨天工作的情况，对于 (1 \leq i \leq 7)，添加从 (i + 16) 到 (i) 的边，边权为 (r[i] - c)，反映该时段需求与雇佣人数的关系。
4. 对于 (8 \leq i \leq 24)，添加从 (i - 8) 到 (i) 的边，边权为 (r[i])，表示从开始工作8小时前到当前小时的需求关系。
5. 添加相邻小时之间的边，从 (i) 到 (i - 1) 的边权为 (-num[i])，从 (i - 1) 到 (i) 的边权为 (0)，表示人数的变化关系。

（四）SPFA算法函数

bool spfa(int c)
{
    build(c);

    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 1;
    dist[0] = 0;
    q[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];
                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;
}

1. 调用 build 函数根据雇佣人数 c 构建图。
2. 初始化距离数组 dist 为极小值，入队次数数组 cnt 为 (0)，节点标记数组 st 为 false。
3. 将源点 0 入队，设置距离为 (0)，标记为在队列中。
4. 当队列不为空时，取出队头节点 t，标记为不在队列中。
5. 遍历节点 t 的所有邻接边，如果通过节点 t 到邻接节点 j 的距离更短，则更新距离 dist[j]，入队次数 cnt[j] 加1。
6. 如果某个节点的入队次数 cnt[j] 达到 (25)（节点数为25个，包括0和1 - 24），说明存在负权回路，返回 false。
7. 如果邻接节点 j 不在队列中，则将其入队并标记为在队列中。
8. 遍历完所有边后，若没有发现负权回路，返回 true。

（五）main 函数

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 1; i <= 24; i ++ ) cin >> r[i];
        cin >> n;
        memset(num, 0, sizeof num);
        for (int i = 0; i < n; i ++ )
        {
            int t;
            cin >> t;
            num[t + 1] ++ ;
        }

        bool success = false;
        for (int i = 0; i <= 1000; i ++ )
            if (spfa(i))
            {
                cout << i << endl;
                success = true;
                break;
            }

        if (!success) puts("No Solution");
    }

    return 0;
}

1. 读取测试用例数量 T。
2. 对于每个测试用例：
   • 读取每个小时的收银员需求数量到 r 数组。
   • 读取申请人数量 n，初始化 num 数组为 (0)，统计每个小时可开始工作的人数。
   • 从 (0) 到 (1000) 枚举雇佣人数 i，调用 spfa 函数判断该人数下是否存在可行方案。
   • 若存在可行方案，输出该人数并标记成功；若所有人数都不可行，输出 No Solution。
3. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 输入和预处理：读取需求和申请人信息，时间复杂度为 (O(T(n + 24)))，其中 (T) 是测试用例数量，(n) 是申请人数量。
2. 二分查找和SPFA算法：枚举雇佣人数最多 (1000) 次，每次调用SPFA算法，SPFA算法在最坏情况下时间复杂度为 (O(mn))，这里 (m) 是边的数量，约为 (24\times2 + 24 + 24 = 72)（构建图的边数），所以这部分时间复杂度为 (O(1000\times mn)=O(1000\times72\times25))。
   总体时间复杂度为 (O(T(n + 24)+1000\times72\times25))。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))，这里 (m) 约为 (72)。
2. 其他数组：需求数组 r[N]、可开始工作人数数组 num[N]、距离数组 dist[N]、队列数组 q[N]、入队次数数组 cnt[N] 和标记数组 st[N]，空间复杂度均为 (O(N))，这里 (N = 30)。
   总体空间复杂度为 (O(N + m)=O(30 + 72)=O(102))。