分析
我们设pre[i]为到第i个时段的雇佣员工的总数量，sum[i]表示时段i的可雇佣员工的总数量，r[i]表示时段i所需工人的数量。由此我们不难求出：
0<=pre[i]-pre[i-1]<=sum[i]
pre[i]-pre[i-8]>=r[i],i∈[8,24]
pre[i-8+24]-pre[i]>=lim-r[i],i∈[0,8]
=>这表示熬夜干活，我们在数轴上画一画可以发现可以表示为pre[i]-pre[i-8]>=r[i]-lim，进而可以得到这个式子
pre[24]-pre[0]>=lim
注意这里面的lim表示雇佣的员工的数量上限。
于是我们可以二分解决。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define pb push_back
#define mp make_pair
int r[50],sum[50],n,d[50],vis[50],iq[50];
vector<pair<int,int> >v[50];
queue<int>q;
inline int spfa(int lim){
memset(vis,0,sizeof(vis));
memset(d,-0x3f,sizeof(d));
memset(iq,0,sizeof(iq));
while(!q.empty())q.pop();
d[0]=0;
vis[0]=1;
q.push(0);
iq[0]=1;
while(!q.empty()){
int x=q.front();
q.pop();
iq[x]=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,z=v[x][i].second;
if(d[y]<d[x]+z){
d[y]=d[x]+z;
if(!iq[y]){
vis[y]++;
if(vis[y]>=25)return 0;
q.push(y);
iq[y]=1;
}
}
}
}
return d[24]==lim;
}
inline int ck(int lim){
int i,j,k;
for(i=0;i<25;i++)v[i].clear();
for(i=1;i<25;i++){
v[i-1].pb(mp(i,0));
v[i].pb(mp(i-1,-sum[i]));
}
for(i=8;i<25;i++)v[i-8].pb(mp(i,r[i]));
for(i=0;i<=8;i++)v[i+16].pb(mp(i,r[i]-lim));
v[0].pb(mp(24,lim));
return spfa(lim);
}
int main(){
int n,m,i,j,k,t,lb,ub;
scanf("%d",&t);
while(t--){
for(i=1;i<=24;i++)scanf("%d",&r[i]);
scanf("%d",&n);
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++){
int x;
scanf("%d",&x);
sum[x+1]++;
}
if(ck(0)){puts("0");continue;}
k=0,lb=0,ub=n;
while(ub-lb>1){
int mid=(lb+ub)>>1;
if(ck(mid))k=1,ub=mid;
else lb=mid;
}
if(k)printf("%d
",ub);
else puts("No Solution");
}
return 0;
}