題目描述
一家超市要每天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≤ti≤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
23
22
1
10
輸出樣例
1
題目分析
對于差分限制的題目，一開始是題目中的找不等式關系。
設num[i] //表示在i時刻申請的人數。 x[i] //表示在i時刻雇傭的人數
不等式關系為：
1.
0<=x[i]<=num[i] //i時刻選擇的人數要大于等于0，小于等于num[i]
2.
x[i-7]+x[i-6]+……+x[i-1]+x[i]>=r[i] //能夠在i時刻服務的人數，一定要大于等于i時刻需要的人數
然後我們會發現：2式不滿足差分限制不等式的基本形式（k[i]>=k[j]+c）。但我們又可以發現：2式是一個連續數的和。是以我們可以用字首和來優化一下該式（因為要用字首和優化，是以我們需要空出0号點，是以我們可以将時間從0-23改為1-24）。
設s[i] //前i個時刻需要雇傭的人數（x[i]的字首和）
優化之後的不等式關系為：
1.
s[i]-s[i-1]>=0 -> s[i]>=s[i-1] //i時刻選擇的人數要大于等于0
2.
s[i]-s[i-1]<=num[i] -> s[i]-num[i]<=s[i-1] //i時刻選擇的人數要小于等于num[i]
3.
能夠在i時刻服務的人數，一定要大于等于i時刻需要的人數。我們需要分段來看：
i>7時：s[i]-s[i-8]>=r[i] -> s[i]>=s[i-8]+r[i]
i<=7時：s[i]+s[24]-s[i+16]>=r[i] -> s[i]>=s[i+16]+r[i]-s[24]
此時，處理最後一個不等式之外，其它所有不等式都滿足差分限制不等式的形式了。那麼如何才能讓該式符合條件呢？我們可以把s[24]看成一個常數，因為n的範圍是[0-1000]。是以我們隻需要枚舉0-1000中的所有數，并将其作為s[24]的值，然後檢查該值是否滿足條件即可。s[24]為1-24時刻内需要的人數之和，我們要求的是所需人數的最小值，是以最小的滿足條件的數即為正确答案。
4.
因為我們将s[24]設為了一個定值，是以在建圖時我們需要見兩條邊來展現一下這一點：s[24]=x => x<=s[24] && s[24]<=x
因為這道題求的是答案的最小值，是以邊要設為：
邊(u,v,w)表示u+w<=v
，并且要求最長路。
再來看看這道題什麼情況下無解：假設目前s[24]=x，如果此時用spfa求解答案時出現了正環，說明該情況不合法。如果枚舉了s[24]所有可能的取值後都不合法，則此題無解。
補：因為我們是從小到大枚舉s[24]，要找出s[24]的最小值，具有單調性。是以我們其實是可以用二分得到s[24]的。
代碼如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=30,M=105,INF=0x3f3f3f3f;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];
int r[N],num[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 s) //根據目前s[24]的值進行建圖
{
idx=0; //先将圖清空
memset(h,-1,sizeof h);
for(int i=1;i<=24;i++)
{
add(i-1,i,0); //不等式1
add(i,i-1,-num[i]); //不等式2
}
for(int i=8;i<=24;i++) add(i-8,i,r[i]); //不等式3的情況1
for(int i=0;i<8;i++) add(i+16,i,r[i]-s); //不等式3的情況2
add(0,24,s),add(24,0,-s); //不等式4
}
bool spfa(int s)
{
build(s);
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
memset(dist,-0x3f,sizeof dist);
queue<int> q;
q.push(0); //設一個虛拟源點0，做為起點
dist[0]=0;
st[0]=true;
while(q.size()) //标準的spfa模闆，不多講了
{
int u=q.front();
q.pop();
st[u]=false;
for(int i=h[u];~i;i=ne[i])
{
int v=e[i];
if(dist[v]<dist[u]+w[i])
{
dist[v]=dist[u]+w[i];
cnt[v]=cnt[u]+1;
if(cnt[v]>=25) return false; //加上0号點之後，一共用25個點
if(!st[v])
{
q.push(v);
st[v]=true;
}
}
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(num,0,sizeof num); //清空num[]數組
int n;
for(int i=1;i<=24;i++) scanf("%d",&r[i]);
scanf("%d",&n);
for(int i=1;i<=n;i++) //統計各個時刻申請的人數
{
int x;
scanf("%d",&x);
num[x+1]++;
}
int l=0,r=n+1; //通過二分計算s[24]的值
while(r>l)
{
int mid=l+r>>1;
if(spfa(mid)) r=mid; //如果目前mid值合法，讓r=mid，看看能不能得到更小的解
else l=mid+1; //否則，讓l=mid+1，加大mid
}
if(r<=n) printf("%d\n",r);
else puts("No Solution");
/* 枚舉法計算s[24]的值
bool flag=false; //記錄是否存在合法解
for(int i=0;i<=1000;i++) //枚舉所有s[24]的值
if(spfa(i))
{
printf("%d\n",i); //如果該情況合法，則之間輸出答案
flag=true;
break;
}
if(!flag) puts("No Solution"); //如果沒有合法情況，此題無解。
*/
}
return 0;
}
![AcWing 藍橋杯AB組輔導課 03、數學與簡單dp[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)