链接
https://www.acwing.com/problem/content/395/
题目
一家超市要每天24小时营业，为了满足营业需求，需要雇佣一大批收银员。
已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。
经理为你提供了一个各个时间段收银员最小需求数量的清单R(0),R(1),R(2),…,R(23)。
R(0)表示午夜00:00到凌晨01:00的最小需求数量，R(1)表示凌晨01:00到凌晨02:00的最小需求数量，以此类推。
一共有N个合格的申请人申请岗位，第 i 个申请人可以从ti时刻开始连续工作8小时。
收银员之间不存在替换，一定会完整地工作8小时，收银台的数量一定足够。
现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。
输入格式
第一行包含一个不超过20的整数，表示测试数据的组数。
对于每组测试数据，第一行包含24个整数，分别表示R(0),R(1),R(2),…,R(23)。
第二行包含整数N。
接下来N行，每行包含一个整数ti。
输出格式
每组数据输出一个结果，每个结果占一行。
如果没有满足需求的安排，输出“No Solution”。
数据范围
(0≤R(0)≤1000,)
(0≤N≤1000,)
(0≤t_i≤23)
输入样例：
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
思路
设(S_i)表示从1到i(方便起见把时间整体右移1h)一共雇佣的员工，那么需要满足一下要求：
(S_i-S-{i-1}≥0) 前缀和性质
(S_i-S_{i-1}≤t_i) 在i时最多可以雇佣的员工数（(t_i)表示可以在这一时开始工作的员工数量）
(S_i-S_{i-8}≥r_i,（i≥8）) i时的员工不能少于顾客数
(S_i+S_{24}-S_{i+16}≥r_i,（i<8）)
前三个等式都可以通过在两点间连边实现，第四个条件有三个变量。数据范围很小，可以通过从小到大枚举(S_{24})的值，表示(S_{24}=c)，建一条从0到24边长为c的边和一条从24到0边长为-c的边，再跑spfa最长路判断是否有解。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=30,M=100;
int h[N],e[M],w[M],nex[M],idx;
int cnt[N],q[N],dis[N];
bool st[N];
int r[N],s[N];
void add(int u,int v,int c){
e[idx]=v;
w[idx]=c;
nex[idx]=h[u];
h[u]=idx++;
}
void build(int c){
memset(h,-1,sizeof h);
idx=0;
for(int i=1;i<=24;++i){
add(i-1,i,0);
}
for(int i=1;i<=24;++i){
add(i,i-1,-s[i]);
}
for(int i=8;i<=24;++i){
add(i-8,i,r[i]);
}
for(int i=1;i<8;++i){
add(16+i,i,r[i]-c);
}
add(24,0,-c);
add(0,24,c);
}
bool spfa(int c){
build(c);
memset(dis,-0x3f,sizeof dis);
memset(cnt,0,sizeof cnt);
memset(st,0,sizeof st);
int hh=0,tt=0;
q[tt++]=0;
st[0]=1;
dis[0]=0;
while(hh!=tt){
int u=q[hh++];
if(hh==N) hh=0;
st[u]=0;
for(int i=h[u];~i;i=nex[i]){
int v=e[i];
if(dis[v]<dis[u]+w[i]){
dis[v]=dis[u]+w[i];
cnt[v]=cnt[u]+1;
if(cnt[v]>=24) return false;
if(st[v]==0){
q[tt++]=v;
if(tt==N)
tt=0;
st[v]=1;
}
}
}
}
return true;
}
int main(){
int T;
cin>>T;
while(T--){
memset(s,0,sizeof s);
for(int i=1;i<=24;++i){
cin>>r[i];
}
int n;
cin>>n;
for(int i=1;i<=n;++i){
int t;
cin>>t;
s[t+1]++;
}
bool f=0;
for(int i=0;i<=1000;++i){
if(spfa(i)){
cout<<i<<endl;
f=1;
break;
}
}
if(!f) cout<<"No Solution
";
}
system("pause");
return 0;
}