分析

• 因为需要求解最小值，因此需要使用最长路。

• 我们使用num数组表示每个时刻来的人数，其中num[1]表示00:00来的人个数，num[24]表示23:00来的人的个数。

• 使用x数组表示最终从num数组中挑选的人的个数，x[1]表示从num[1]中挑选的人的个数，x[24]表示从num[24]中挑选的人的个数。

• 使用r数组表示每个时刻需要的人的个数，r[1]表示00:00需要的人的个数，r[24]表示23:00需要的人的个数。则有下列不等式：

（1）$0 \le x_i \le num[i]$；

（2）$x_{i-7} + x_{i-6} + … + x_i \ge r_i$；

• 上面的式子不符合差分约束中的不等式，因此需要进行变换，这里采用前缀和的技巧，令S[0]=0，S[i] = $\sum x_i$，则我们需要求解$S_{24}$的最小值。则上面不等式可以变为：

（1）$0 \le S_i - S_{i-1} \le num[i]，1 \le i \le 24$；

（2）$i \ge 8, 则S_i - S_{i-8} \ge r_i$或者$0<i \le 7，则S_i + S_{24} - S_{i+16} \ge r_i$；

• 整理上述不等式得到：

（1）$S_i \ge S_{i-1} + 0，1 \le i \le 24$;

（2）$S_{i-1} \ge S_i - num[i]，1 \le i \le 24$;

（3）$i \ge 8$， 则$S_i \ge S_{i-8} + r_i$;

（4）$0<i\le 7$，则;$S_i \ge S_{i+16} - S_{24} + r_i$；

• 我们发现第（4）个不等式不满足差分约束的不等式，因为$S_{24}$也是变量，这里采取的策略是可以枚举该变量的所有值，这样就可以将$S_{24}$看成常量了。因为最多有1000个人申请，所以$S_{24}$取值范围是[0, 1000]。，假设将$S_{24}$固定为c，则$S_{24}==c$，所以有下列不等式：

（5）$S_{24} \ge S_0 + c$，并且$S_0 \ge S_{24} - c$；

• 加上0号值为0（dist[0] = 0）的点，图中一共有25个点，有70多条边，因此枚举1000多次是完全可行的。

• 另外根据不等式$S_i \ge S_{i-1} + 0，1 \le i \le 24$，0号点可以到达其余所有点，因此可以达到所有边。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30, M = 100;

int n;  // 申请岗位的人数
int h[N], e[M], w[M], ne[M], idx;
int r[N], num[N];  // num数组表示每个时刻来的人数
int dist[N];
int q[N], 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++;
}

void build(int c) {

    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, -c + r[i]);
    add(0, 24, c), add(24, 0, -c);
}

// c: 分析中的s24，返回是否存在答案
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 = 0;
    q[tt++] = 0;
    st[0] = true;
    dist[0] = 0;

    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--) {

        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;
}