莫欺少年穷，修魔之旅在这开始—>算法提高课题解

差分约束 + 枚举

思路：

1. 求最小值即求最长路（正环）
2. x[i] 表示当前时段的人数，s[i] 表示 x[1~i] 的总人数，num[i] 表示当前时段来的人数
3. 0 <= s[i] - s[i-1] <= num[i]：s[i] >= s[i-1] + 0；s[i-1] >= s[i] - num[i]
4. 8 <= i <= 24：s[i] >= s[i-8] + r[i]
5. 1 <= i <= 7：s[i] >= s[i+16] + r[i] - s[24]
6. 建立虚拟原点 0，保证可以遍历到所有点：s[24] >= s[0] + s24；s[0] >= s[24] - s24
7. 从 0 开始枚举这个 s24 是否符合条件，如果存在正环，即不符合，反之符合

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 30, M = 100;

int n;
int r[N],num[N];
int h[N],e[M],w[M],ne[M],idx;
int dist[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 s24)
{
    //多组数据需要初始化
    memset(h,-1,sizeof h);
    idx=0;

    for(int i=1;i<=24;i++)
    {
        add(i-1,i,0); // s[i] >= s[i-1] + 0
        add(i,i-1,-num[i]); // s[i-1] >= s[i] - num[i]
    }

    for(int i=8;i<=24;i++) add(i-8,i,r[i]); // s[i] >= s[i-8] + r[i]

    for(int i=1;i<=7;i++) add(i+16,i,r[i]-s24); // s[i] >= s[i+16] + r[i] - s[24]

    add(0,24,s24),add(24,0,-s24); // s[24] = s[0] + s24；s[0] = s[24] - s24
}

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

    //多组数据需要初始化
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    memset(dist,-0x3f,sizeof dist);
    dist[0]=0;

    queue<int> q;
    q.push(0);
    st[0]=true;

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        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.push(j);
                    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 flag=false;
        for(int i=0;i<=1000;i++)
            if(spfa(i))
            {
                cout<<i<<endl;
                flag=true;
                break;
            }

        if(!flag) cout<<"No Solution"<<endl;
    }

    return 0;
}