「一本通 3.4 例 2」出纳员问题

形式化题目

每天分 24 个小时段，第 $i$ 段（ $i$ 时到 $i+1$ 时， $0 \le i \le 23$ ）至少需要 $R(i)$ 名出纳员在岗。

有 $N$ 名申请者，第 $j$ 人若被雇佣，将从 $t_j$ 时开始恰好连续工作 8 小时，即覆盖小时段

t_j,\ t_j+1,\ \dots,\ t_j+7 \pmod{24}.

注意时间是按 24 小时循环的： $t_j = 23$ 的人覆盖 $23, 0, 1, 2, 3, 4, 5, 6$ 。

记 $c_i$ 为满足 $t_j = i$ 的申请者人数。选择一组雇佣变量 $x_i$ （从 $i$ 时开始且被雇佣的人数， $0 \le x_i \le c_i$ ），使每个小时段的在岗人数不少于需求：

\sum_{k=0}^{7} x_{(i-k) \bmod 24} \ \ge\ R(i), \qquad i = 0,1,\dots,23,

在满足全部约束的前提下最小化总雇佣人数 $M = \sum_{i=0}^{23} x_i$ 。若不存在任何可行方案，输出 No Solution。

样例覆盖关系：下表中 ● 表示该申请人覆盖了对应小时段，R 行是需求。

申请人 $t_j$	0	1	2	3	4	5	6	7	22	23
0	●	●	●	●	●	●	●	●
1		●	●	●	●	●	●	●
10
22	●	●	●	●	●	●	●		●	●
23	●	●	●	●	●	●	●			●
$R(i)$	1	0	1	0	0	0	1	0	0	1

只雇佣 $t = 23$ 的这一个人，他覆盖 $23, 0, 1, \dots, 6$ ，恰好命中全部 4 个需求为 1 的小时段（ $0, 2, 6, 23$ ），其余小时段需求为 0，所以答案是 $1$ 。注意 $t = 22$ 的人覆盖不到小时段 6， $t=0$ 的人覆盖不到小时段 23，都单独不够用。

正解

思路

为什么不能贪心。 一个人覆盖连续 8 小时，所以 $x_i$ 会同时出现在 8 条小时段约束里。若从 0 时开始逐小时检查、不够就补人，"补在哪个时刻"会影响后面 8 小时，补得早可能浪费、补得晚可能漏掉当前需求，局部选择无法保证全局最优。枚举子集又是 $2^N$ （ $N \le 1000$ ），不可行。

第一步：用前缀和把"区间求和"变成"两点之差"。

令前缀和

S(i) = x_0 + x_1 + \dots + x_{i-1}, \qquad S(0) = 0, \qquad S(24) = M.

于是 $x_i = S(i+1) - S(i)$ ，而小时段约束里的"连续 8 项之和"正好可以写成两个 $S$ 相减：

\text{cover}(i) = \begin{cases} S(i+1) - S(i-7), & i \ge 7,\\[4pt] \bigl(S(24) - S(i+17)\bigr) + S(i+1), & i < 7. \end{cases}

为什么 $i<7$ 时多了 $S(24)-S(i+17)$ 。 覆盖小时段 $i$ （ $i<7$ ）的人，起始时刻是 $\{i-7, \dots, -1\} \cup \{0, \dots, i\}$ ，用模 24 写就是 $\{i+17, \dots, 23\} \cup \{0,\dots,i\}$ 。前一段在今天的贡献是 $S(24) - S(i+17)$ （从 $i+17$ 时到 24 时开始的人），后一段是 $S(i+1) - S(0)$ 。两段相加即得上式。

第二步：把目标 $M$ 变成约束。

$M = S(24)$ 本来是要最小化的目标。但我们注意到它的取值范围很小： $M \in [0, N] \subseteq [0, 1000]$ 。于是可以枚举 $M$ ，用两条边把它钉死：

S(24) \ge S(0) + M, \qquad S(0) \ge S(24) - M.

这样"求最优"就变成了"判定某个 $M$ 是否可行"。

第三步：可行性关于 $M$ 单调，所以二分。

若 $M$ 有可行方案 $H$ ，且 $M < N$ ，则必有一个申请者 $j \notin H$ ；把他一并雇上，所有小时段的人数只增不减，约束仍然满足，于是 $M+1$ 也可行。所以存在分界点 $M^*$ ： $M < M^*$ 不可行、 $M \ge M^*$ 可行。在 $[0,N]$ 上二分，只需 $O(\log N)$ 次判定。

第四步：判定就是差分约束 + 最长路。

把每条不等式 $S(v) \ge S(u) + w$ 建成有向边 $u \to v$ 、权 $w$ ，就得到一个差分约束系统：

含义	不等式	边
前缀不减（ $x_i \ge 0$ ）	$S(i+1) \ge S(i)$	$i \to i+1$ ，权 $0$
人数上界（ $x_i \le c_i$ ）	$S(i) \ge S(i+1) - c_i$	$i+1 \to i$ ，权 $-c_i$
同一天需求（ $i \ge 7$ ）	$S(i+1) \ge S(i-7) + R(i)$	$i-7 \to i+1$ ，权 $R(i)$
跨午夜需求（ $i < 7$ ）	$S(i+1) \ge S(i+17) + R(i) - M$	$i+17 \to i+1$ ，权 $R(i) - M$
钉死总人数	$S(24) \ge S(0) + M$ 、 $S(0) \ge S(24) - M$	$0 \to 24$ 权 $M$ ， $24 \to 0$ 权 $-M$

这类系统的最长路解 $d$ 是"逐分量最小的可行解"：任何可行解都必须处处不小于 $d$ （沿最长路归纳），而无正环时 $d$ 本身满足全部边。把 25 个距离初值全设为 0 并全部入队，等价于加一个超级源点向每个点连 0 权边，一轮即可从所有点出发。

因此判定 $M$ 的方法就是：跑最长路，若出现正环说明约束自相矛盾，返回不可行；否则检查 $d(24) \ge M$ （配合钉死边，实际就是 $d(24) = M$ ）。

下面是样例对应的约束图：粗链是前缀不减的 $S(0) \to \dots \to S(24)$ ，跨段弧是需求边（ $i\ge7$ 向"后"取 $S(i-7)$ ， $i<7$ 向"前"取 $S(i+17)$ ）。

flowchart LR
  S0["S(0)"] --> S1["S(1)"] --> S2["S(2)"] --> S7["S(7)"] --> Sx["..."] --> S17["S(17)"] --> S18["S(18)"] --> S23["S(23)"] --> S24["S(24)"]
  S17 -.->|"R(0) - M"| S1
  S18 -.->|"R(1) - M"| S2
  S23 -.->|"R(6) - M"| S7
  S0 -.->|"R(7)"| S8["S(8)"]
  S16["S(16)"] -.->|"R(23)"| S24

读图要点：需求边不一定沿链的方向。 $i \ge 7$ 时它从 $S(i-7)$ 指向 $S(i+1)$ （沿链向右，例如 $S(0) \to S(8)$ 与 $S(16) \to S(24)$ ）； $i < 7$ 时它从 $S(i+17)$ 指向 $S(i+1)$ （逆着链向左，例如 $S(17) \to S(1)$ 、 $S(23) \to S(7)$ ）——这正是跨午夜时段必须借助 $M$ 才能表达的几何来源。链边保证 $S$ 单调，使最长路的解能还原出合法的 $x_i \ge 0$ 。

图中每条链边 $S(i) \to S(i+1)$ 权 $0$ ，反向的 $S(i+1) \to S(i)$ 权 $-c_i$ 为清晰起见省略。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 15:31
# update_at: 2026-09-30 15:31

import sys
from collections import deque

HOURS = 24   # 一天 24 个整点区间
SHIFT = 8    # 每人连续工作恰好 8 小时


def feasible(adj: list[list[tuple[int, int]]], target: int) -> bool:
    """跑最长路判断约束是否相容，并检查 S(24) 恰好等于 target。

    差分约束中 S(24) >= target 与 S(24) <= target 两条边已把 S(24) 钉死；
    若约束互相矛盾就会出现正环，此时某点会被反复松弛，超过 HOURS 轮即可判定。
    """
    dist = [0] * (HOURS + 1)
    in_queue = [True] * (HOURS + 1)
    queue = deque(range(HOURS + 1))  # 超级源点：所有点一起入队，等价于各连一条 0 权边
    rounds = [0] * (HOURS + 1)       # 每个点被成功松弛的次数，超过 HOURS 次说明有正环
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        du = dist[u]  # 弹出时才读，保证用的是 u 的最新距离
        for v, w in adj[u]:
            if du + w > dist[v]:
                dist[v] = du + w
                rounds[v] += 1
                if rounds[v] > HOURS:
                    return False  # 正环：约束互相矛盾
                if not in_queue[v]:
                    in_queue[v] = True
                    queue.append(v)
    return dist[HOURS] >= target


def build(need: list[int], supply: list[int], total: int) -> list[list[tuple[int, int]]]:
    """按前缀和 S(i) = x(0)+...+x(i-1) 建图，边 (v, w) 表示 S(v) >= S(u) + w。

    need[i] 是第 i 个整点区间的需求 R(i)，supply[i] 是 t_i = i 的申请人数，
    total 是假定的总雇佣人数 M = S(24)。
    """
    adj: list[list[tuple[int, int]]] = [[] for _ in range(HOURS + 1)]
    for i in range(HOURS):
        adj[i].append((i + 1, 0))            # S(i+1) >= S(i)：前缀不减，即 x(i) >= 0
        adj[i + 1].append((i, -supply[i]))   # S(i) >= S(i+1) - c(i)：x(i) <= c(i)
    for i in range(HOURS):
        start = i - SHIFT + 1                                   # 覆盖第 i 小时的起点区间左端
        if start >= 0:
            adj[start].append((i + 1, need[i]))                 # 同一天：S(i+1) - S(start) >= R(i)
        else:
            # 跨午夜：S(i+1) + (M - S(i+17)) >= R(i)，即 S(i+1) >= S(i+17) + R(i) - M
            adj[start + HOURS].append((i + 1, need[i] - total))
    adj[0].append((HOURS, total))            # S(24) >= S(0) + M
    adj[HOURS].append((0, -total))           # S(0) >= S(24) - M，把 S(24) 锁成 M
    return adj


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        need = [next(data) for _ in range(HOURS)]
        n = next(data)
        supply = [0] * HOURS  # 每个起始时刻的申请者人数，即 x(i) 的上界
        for _ in range(n):
            supply[next(data)] += 1

        # 可行性对 M 单调：多雇一个已申请的人不会破坏任何时段，故二分最小 M。
        lo, hi = 0, n
        while lo < hi:
            mid = (lo + hi) // 2
            if feasible(build(need, supply, mid), mid):
                hi = mid
            else:
                lo = mid + 1

        out.append(str(lo) if feasible(build(need, supply, lo), lo) else "No Solution")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:32
 * update_at: 2026-10-05 05:32
 */
// 差分约束 + 二分答案：
// 设 S(i) = x(0) + x(1) + ... + x(i-1)，其中 x(i) 是 t = i 的被雇佣人数，S(24) = M 为总雇佣人数。
// 每个小时段 i 的在岗人数是起始时刻落在 {i-7, ..., i} (mod 24) 的人数和，写成前缀和之差后，
// 逐条约束都是 S(v) >= S(u) + w 的形式；把 M 用两条互反的边钉死，判定就变成最长路是否出现正环。
// 可行性关于 M 单调（多雇一人只会让人数变多），所以在 [0, N] 上二分最小可行的 M。

#include <bits/stdc++.h>
using namespace std;

const int HOURS = 24;    // 一天 24 个小时段
const int SHIFT = 8;     // 每人连续工作恰好 8 小时
const int NODES = 25;    // 前缀和节点 S(0) ~ S(24)
const int MAXEDGE = 128; // 边数上限：24 * 2 条链边 + 24 条需求边 + 2 条钉死边 = 74

typedef long long ll;

// 链式前向星存图，每条边表示约束 S(v) >= S(u) + w
int head[NODES], to[MAXEDGE], nxt[MAXEDGE], edge_cnt;
int weight[MAXEDGE];

int need[HOURS];    // need[i] = R(i)，第 i 个小时段最少需要的在岗人数
int supply[HOURS];  // supply[i] = 起始时刻为 i 的申请者人数，即 x(i) 的上界
ll dist[NODES];     // 最长路距离，最长路解是逐分量最小的可行前缀和
bool in_queue[NODES];  // 该节点当前是否在 SPFA 队列中
int relax_cnt[NODES];  // 每个点被成功松弛的次数，超过 NODES 次说明存在正环

// 加一条 u -> v、权 w 的边。
void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 按假定的总雇佣人数 total 建图（total = S(24)）。
void build_graph(int total) {
    edge_cnt = 0;
    for (int i = 0; i < NODES; i++) head[i] = 0;
    for (int i = 0; i < HOURS; i++) {
        add_edge(i, i + 1, 0);           // S(i+1) >= S(i)：前缀不减，即 x(i) >= 0
        add_edge(i + 1, i, -supply[i]);  // S(i) >= S(i+1) - c(i)：x(i) <= c(i)
    }
    for (int i = 0; i < HOURS; i++) {
        int start = i - SHIFT + 1;  // 覆盖小时段 i 的起始时刻区间左端
        if (start >= 0) {
            add_edge(start, i + 1, need[i]);  // 同一天：S(i+1) - S(start) >= R(i)
        } else {
            // 跨午夜：S(i+1) + (S(24) - S(i+17)) >= R(i)，即 S(i+1) >= S(i+17) + R(i) - M
            add_edge(start + HOURS, i + 1, need[i] - total);
        }
    }
    add_edge(0, HOURS, total);   // S(24) >= S(0) + M
    add_edge(HOURS, 0, -total);  // S(0) >= S(24) - M，两条边把 S(24) 锁成 M
}

// 判定总雇佣人数为 total 时是否存在可行方案：跑最长路，有正环则约束矛盾。
bool feasible(int total) {
    build_graph(total);
    queue<int> q;
    for (int i = 0; i < NODES; i++) {
        dist[i] = 0;         // 全部初值为 0 并入队，等价于超级源点向各点连 0 权边
        in_queue[i] = true;
        relax_cnt[i] = 0;
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            if (dist[u] + weight[e] > dist[v]) {
                dist[v] = dist[u] + weight[e];
                relax_cnt[v]++;
                if (relax_cnt[v] > NODES) return false;  // 正环：约束互相矛盾
                if (!in_queue[v]) {
                    in_queue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dist[HOURS] >= total;
}

void solve() {
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < HOURS; i++) scanf("%d", &need[i]);
        int n;
        scanf("%d", &n);
        for (int i = 0; i < HOURS; i++) supply[i] = 0;
        for (int i = 0; i < n; i++) {
            int start_hour;
            scanf("%d", &start_hour);
            supply[start_hour]++;
        }

        // 可行性对 M 单调：多雇一个申请人不会让任何小时段的人数减少，故二分最小 M。
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (feasible(mid)) hi = mid;
            else lo = mid + 1;
        }
        if (feasible(lo)) printf("%d\n", lo);
        else printf("No Solution\n");
    }
}

int main() {
    solve();
    return 0;
}

复杂度

设 $V = 25$ 、 $E \le 74$ （ $= 24 \times 2 + 24 + 2$ ）。

单次判定：SPFA 最长路，无正环时每点最多被松弛 $O(V)$ 次，每次扫其出边，故 $O(VE)$ ，且 $V, E$ 都是与 $N$ 无关的常数。
二分： $O(\log N)$ 次判定， $N \le 1000$ 时至多 10 次。
单组总时间 $O(N + \log N \cdot VE)$ ，空间 $O(N + V + E)$ 。

与 C++ 正解（差分约束 + 二分答案）同阶，只差常数因子。由于 $V = 25$ ， Python 侧实测 24 组数据合计 0.024s、峰值内存约 15MB，不存在 TLE/MLE 风险。

总结

本题的关键是把"连续 8 小时的区间计数"翻译成前缀和的差，从而让每条小时段约束都变成一对变量之间的不等式；再用"枚举总数 $M$ 并钉死 $S(24)=M$ "把最优化降级为判定，用 $M$ 的单调性把枚举换成二分，最后交给差分约束的最长路。

三个容易写错的地方：

跨午夜的需求边权必须减 $M$ ，即 $S(i+1) \ge S(i+17) + R(i) - M$ ，漏掉 $-M$ 会让样例直接判成 No Solution；
钉死 $S(24) = M$ 需要两条方向相反的边，只加一条会让判定对过大的 $M$ 误判为可行；
正环检测用"某点被成功松弛超过 $V$ 次"来判定，不要在 SPFA 里漏掉这个出口，否则矛盾输入会死循环。

图示解析

跨午夜是本题唯一的几何障碍。下表列出"覆盖小时段 $i$ 的起始时刻集合"在午夜处被切成两段的情形，它正是要求 $i<7$ 时边权减去 $M$ 的原因。

小时段 $i$	覆盖它的起始时刻 $\{i-7,\dots,i\} \bmod 24$	被午夜切成的两段	覆盖人数
$i \ge 7$ （如 $i=23$ ）	$16,17,\dots,23$	不切分，就是一段	$S(24)-S(16)$
$i = 6$	$23,0,1,2,3,4,5,6$	$[23,23]$ 与 $[0,6]$	$(S(24)-S(23)) + S(7)$
$i = 0$	$17,18,\dots,23,0$	$[17,23]$ 与 $[0,0]$	$(S(24)-S(17)) + S(1)$

观察重点：

判断一个起始时刻是否覆盖小时段 $i$ ，等价于判断 $t \in \{i-7, \dots, i\} \pmod{24}$ ；当 $i < 7$ 时这个集合被午夜切成两段，所以覆盖人数是两个前缀差之和，其中靠前的那段含 $S(24)$ 。
因为 $S(24) = M$ 正是要枚举的量，这条边的权里就必然出现 $M$ ；这也是"每个候选 $M$ 都要重新建图"的原因。
对比 $i=23$ 与 $i=6$ ：前者起点是一段连续下标，后者被拆成 $23$ 和 $0..6$ 两个片段—— 这种"跨过午夜回绕"正是循环时间带来的唯一麻烦，也是前缀和下标要用 $i+17$ 而不是 $i-7$ 的原因。

验证情况：3 个真实数据文件共 24 组全部通过；与指数级暴力在 1005 组随机小数据上逐行一致， 0 处不符；并实测确认可行性关于 $M$ 严格单调（24 组真实数据上 0 处违反），二分成立。