// 本文也可以在我的blog: arintaro.com看

Description:

@card{

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

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

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

$R(0)$表示午夜到凌晨一点的最小需求数量，$R(1)$表示凌晨一点到凌晨两点的最小需求数量，以此类推。

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

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

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

}

Solution:

@card{

先考虑贪心，显然对一个选完的前缀接下来选能选的向后扩展最长的收银员最好，但是这个问题是一个”环形”问题，由于可能不存在常规环形问题的”断点”，是没法直接转换成序列上的问题的。

常规的思路是在一个中间局面考虑某个收银员是否选择，但差分约束的思路是求出一组解，再考虑现在的收银员能否满足这组解，有点像”生成-验证”的暴力？

有了这个思路就好办了，我们可以先对需要最优化的值求前缀和，再应用差分约束，具体到这个问题上就是某个前缀雇佣了多少收银员，然后对每个时间去计算”当前在工作的收银员的上班时间”，同时注意环形性质即可，具体计算可以设元解不等式。

方便起见，下面的方程下标均加了一。

具体写出方程后，发现有一个方程是$dist[24] - dist[i + 16] + dist[i] \geq arr[i]$，有三个变量，无法应用差分约束，但是对于一个确定的$i$，其中只有两项是”动态的”，所以我们考虑枚举$dist[24]$，验证是否存在解即可，注意$dist[24]$其实就是答案，而它显然具有单调性，换成二分答案时间上会更优。

具体实现上，与常规的差分约束不同，我们有了一个已知的”定值”，如何应用这个条件呢？

1. 不额外加边，直接初始化$dist[24] = mid$，并用其作源点跑最长路。
   这是一个错误的想法，因为差分约束维护的不是具体的值，而是元素之间的差，这使得所有元素加上一个任意值，图中的不等式也都是成立的。跑完最长路后，图中的$dist$值的确满足我们设下的限制关系，并且$dist[24]$也一定不会改变，否则图中存在正环，无解，但是求出的解可能会没有实际意义，因为$dist[0]$可能不等于0。

2. 不额外加边，直接初始化$dist[0] = 0$，$dist[24] = mid$，并直接入队两个点跑最长路。
   这也是一个错误的想法，因为初始化两个源点的值，而不将他们的值设成$-inf$，即使在没有正环的情况下，两个源点中的一个也可能会被另外一个更新，导致与初始化的条件不符。

3. 额外加边$dist[24] \geq mid$，$dist[24] \leq mid$，并初始化$dist[0] = 0$作为源点跑最长路。
   这是正确的，这样显然可以保证$dist[24] = mid$，并且$dist[0]$的值不会被意外更新。如果被更新，图中一定存在正环，无解。在其他差分约束问题中，还要注意源点是否能遍历全图，如果图中不存在负环/正环，被扫描过的边代表的限制条件是一定成立的，但是图也可能是不联通的，此时需要设计超级源点，尽量不要一次入队全部节点，这样初值的设计非常麻烦。

4. 额外加边，随便初始化一个点，随便初始化一个大于$-inf$的值。
   这也是正确的，只要保证初始化的这个点能够遍历全图，这是差分约束系统”差分性质”的更好体现，我们额外加的边约束了$0$与$24$的关系，求出一组解后，只要把这组解的值全部减去$dist[0]$，一定能对应一组有实际意义的解。

在一般问题中，我们一般采用做法3，对于已知的常量，不初始化维护，而通过与”基点”的两个不等式去维护。

}

Code:

@card{

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define rint register int
#define lint long long
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
    int f = 1; char ch = getchar(); x = 0;
    for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= f;
}
using namespace std;
const int maxn = 24 + 10;
const int maxm = 1000 + 10;

int n = 24, m;
int arr[maxn], cnt[maxn], sum_cnt = 0;
int head[maxn], ev[maxm], ew[maxm], nxt[maxm], totedge = 1;
inline void addedge(int nu, int nv, int nw) {
    ev[++totedge] = nv, ew[totedge] = nw;
    nxt[totedge] = head[nu], head[nu] = totedge;
}
void clear() {
    memset(arr, 0 ,sizeof(arr)), memset(cnt, 0, sizeof(cnt));
    sum_cnt = 0;
}

int dist[maxn], cnt_path[maxn];
bool inq[maxn];
queue<int> q;

bool check(int x) {
    memset(inq, 0, sizeof(inq));
    memset(cnt_path, 0, sizeof(cnt_path));
    memset(head, 0, sizeof(head)), totedge = 1;
    memset(dist, 0xcf, sizeof(dist));

    dist[0] = 0;
    for(rint k=1; k<=7; k++) addedge(k + 16, k, arr[k] - x);
    for(rint k=8; k<=24; k++) addedge(k - 8, k, arr[k]);
    for(rint k=1; k<=24; k++) addedge(k, k-1, -cnt[k]), addedge(k-1, k, 0);
    addedge(0, 24, x), addedge(24, 0, -x);
    while(q.size()) q.pop();

    q.push(0), inq[0] = 1;
    while(!q.empty()) {
        int x = q.front(); q.pop(), inq[x] = 0;
        for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
            if(dist[y] < dist[x] + ew[i]) {
                dist[y] = dist[x] + ew[i];
                cnt_path[y] = cnt_path[x] + 1;
                if(cnt_path[y] > n + 1) return 0;
                if(inq[y] == 0) inq[y] = 1, q.push(y);
            }
        }
    }
    return 1;
}

int main() {
    int T;
    readint(T);
    while(T--) {
        clear();
        for(rint i=1; i<=n; i++) readint(arr[i]);
        readint(m);
        int x = 0;
        for(rint i=1; i<=m; i++) readint(x), cnt[x + 1]++;

        int l = 0, r = m + 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(l == m + 1) puts("No Solution");
        else printf("%d\n", l);
    }
    return 0;
}

}