1510：【例 2】出纳员问题

题目描述

原题来自：Asia 2000

Tehran 的一家每天 24 小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员（例如，午夜时只需要一小批，而下午则需要很多）为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供给你一天的每一小时需要出纳员的最少数量——$R(0), R(1), \cdots, R(23)$。$R(0)$ 表示从午夜到上午 1:00 需要出纳员的最小数目，$R(1)$ 表示上午 1:00 到 2:00 需要的，等等。每一天，这些数据都是相同的。有 $N$ 人申请这项工作，每个申请者 $i$ 在每 24 小时中，从一个特定的时刻开始连续工作恰好 8 小时，定义 $t_i$ 为上面提到的开始时刻。也就是说，如果第 $i$ 个申请者被录取，他（她）将从 $t_i$ 时刻开始连续工作 8 小时。

请你编写一个程序，输入 $R(i)$ 和 $t_i$，它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的 $R(i)$ 更多的出纳员在工作。

输入格式

第一行为测试点的数目 $T$。

对于每组测试数据：

• 第一行为 24 个整数，表示 $R(0), R(1), R(2), \cdots, R(23)$；
• 接下来一行一个正整数 $N$，表示申请者数目；
• 接下来 $N$ 行每行一个整数 $t_i$。

两组测试数据之间没有空行。

输出格式

对于每个测试点，输出一行，包含一个整数，表示需要出纳员的最小数目。如果无解，输出 No Solution。

样例

样例输入 #1

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

1

样例解释 #1

• 一天 24 小时每个小时需要的最少出纳员数量：
  • $R(0)=1$（0:00-1:00 需要至少 1 人）
  • $R(1)=0$（1:00-2:00）
  • $R(2)=1$（2:00-3:00）
  • $R(3)=0$（3:00-4:00）
  • ...
  • $R(22)=0$（22:00-23:00）
  • $R(23)=1$（23:00-0:00）
• 有 $N=5$ 个申请者，开始工作时间 $t_i$ 分别为：$0, 23, 22, 1, 10$。
• 一个申请者如果在 $t_i$ 开始工作，将连续工作 8 小时，覆盖 $t_i, t_i+1, \ldots, t_i+7$（模 24 小时，例如 $t_i=23$ 则覆盖 23,0,1,...,6）。
• 最少需要雇佣 1 个出纳员，可以雇佣 $t_i=0$ 的申请者，他的工作时间覆盖 0:00-8:00，满足 $R(0)=1, R(2)=1$ 等时段的需求。其他时段 $R$ 要求为 0，所以 1 人足够。
• 注意：虽然 $R(23)=1$，但 $t_i=0$ 的申请者不覆盖 23:00-0:00，不过 $R(23)$ 可以由 $t_i=23$ 的申请者覆盖，但为了最小化雇佣人数，我们可以不雇佣他，因为 $R(23)$ 实际上可以被覆盖吗？检查：$t_i=23$ 的申请者覆盖 23,0,1,...,6，其中 $R(23)$ 被覆盖。但如果我们只雇佣 $t_i=0$，$R(23)$ 无人覆盖，不满足要求。所以样例可能还有别的解释。

实际上，样例中 $R(23)=1$ 且 $t_i=23$ 有一个申请者，如果我们雇佣 $t_i=23$ 的人，他覆盖 23,0,1,...,6，同时满足 $R(0)=1$ 和 $R(23)=1$，因此只需要雇佣 1 人（$t_i=23$）即可满足所有时段需求。输出 1。

数据范围

对于全部数据：

• $1 \le T \le 20$
• $0 \le N \le 1000$
• $0 \le R(i) \le 1000$
• $0 \le t_i \le 23$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题可以转化为差分约束系统。设 $S[i]$ 表示从 0 时刻到 $i$ 时刻（包括 $i$）雇佣的出纳员总数（$i$ 从 0 到 24，$S[24]$ 表示总雇佣人数，即答案）。约束包括：

1. 每个时刻 $i$ 实际工作人数不少于 $R(i)$。
2. 每个申请者 $t_i$ 可以选择雇佣或不雇佣，雇佣则在其工作的 8 小时内贡献 1。
3. 可以二分总人数 $S[24]$，然后判断是否存在可行解。
4. 具体地，设 $x[i]$ 表示在 $i$ 时刻开始工作的人数（即 $t_j=i$ 的申请者被雇佣的数量），则 $S[i] = \sum_{k=0}^{i-1} x[k]$（因为 $S[i]$ 是到 $i$ 时刻为止开始工作的人数，注意工作持续 8 小时）。
5. 时刻 $i$ 的实际工作人员为过去 8 小时内开始工作的人数之和：$x[i-7]+x[i-6]+\cdots+x[i]$（模 24 处理）。
6. 转化为差分约束：$S[i+1] - S[i] \ge 0$，$S[i+1] - S[i] \le num[i]$（其中 $num[i]$ 是 $t_j=i$ 的申请者总数），以及 $S[i] - S[j] \ge R(i)$ 对于某些 $i,j$（根据工作覆盖关系）。 由于 $N \le 1000$，$T \le 20$，可以通过二分+差分约束求解。