AcWing 393. 雇傭收銀員（差分限制）

Description

一家超市要每天 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 小時，收銀台的數量一定足夠。

現在給定你收銀員的需求清單，請你計算最少需要雇傭多少名收銀員。

Input

第一行包含一個不超過 20 的整數，表示測試資料的組數。

對于每組測試資料，第一行包含 24 個整數，分别表示 R(0),R(1),R(2),…,R(23)(0≤R(i)≤1000)。

第二行包含整數 N(0≤N≤1000)。

接下來 N 行，每行包含一個整數 ti(0≤ti≤23)。

Output

每組資料輸出一個結果，每個結果占一行。

如果沒有滿足需求的安排，輸出 

No Solution

。

Sample Input

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

Sample Output

1

思路：利用差分限制求最小值：答案的最小值等于答案的最大上界，是以我們需要找出題目中帶有‘ ≥ ’符号的不等式。

利用字首和S[i]表示前i小時即[00:00, i - 1:00]雇傭的收銀員人數，是以可以找出S[i]滿足以下不等式：

1. 每個時間段雇傭收銀員的人數 ≥ 0：S[i] - S[i - 1] ≥ 0 → S[i] ≥ S[i - 1] + 0 → add(i - 1, i, 0);

2. 每個時間段雇傭收銀員的人數 ≤ 該時間段收銀員的申請人數：

    S[i] - S[i - 1] ≤ r[i]  →  S[i - 1] ≥ S[i] - r[i]  →  add(i, i - 1, -r[i]);

3. 需要滿足題目要求，使得需求清單的時間段上有收銀員工作：

  對于7 ≤ i ≤ 23 的時間段需要滿足：

  S[i + 1] - S[i + 1 - 8] ≥ need[i]  →  S[i + 1] ≥ S[i + 1 - 8] +need[i]  →  add(i + 1 - 8, i + 1, need[i]);

  對于0 ≤ i ≤ 6 的時間段需要滿足：

  S[i + 1] + S[24] - S[16 + i + 1] ≥ need[i]  →  S[i + 1] ≥ S[16 + i + 1] -S[24] + need[i] → add(16 + i + 1, i + 1, -S[24] + need[i]);

注意：這裡我們并不知道S[24]的取值，但我們可以知道0≤N≤1000，是以0≤S[24]≤1000。是以我們隻需要從小到大周遊S[24]的取值，如果出現一個取值滿足以上不等式且不發生沖突，則該值為S[24]的最小取值，即為答案[00:00, 24 - 1:00]時間段雇傭的收銀員人數。

4.在周遊時，我們還需要添加S[24] = i 這條不等式，我們可将其轉化為S[24] ≥ i，S[24] ≤ i，又因為S[0]沒有被用到，其值為0，是以S[24] ≥ S[0] + i，S[24] ≤ S[0] + i  →  add(0, 24, i); add(24, 0, -i);

注意：我們空出來的S[0]剛好可以作為一個超級源點，是以求spfa時從0出發即可

證明：因為add(i-1, i, 0)，是以有0→1→2→…→50000，是以0可以到達每一個點，滿足超級源點的性質

代碼如下：

#include<bits/stdc++.h>
using namespace std;

#define N 30
#define M 1000

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int need[N], r[N];
void build(int s24) {
	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, -r[i]);
	for (int i = 8; i <= 24; i++)add(i - 8, i, need[i]);
	for (int i = 1; i <= 7; i++)add(16 + i, i, -s24 + need[i]);
	add(0, 24, s24), add(24, 0, -s24);
}

int dist[N], st[N], cnt[N];
bool spfa(int s24) {
	build(s24);
	memset(dist, -0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	memset(cnt, 0, sizeof cnt);

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

	while (q.size()) {
		int t = q.front();
		q.pop();
		st[t] = 0;

		for (int i = h[t]; i != -1; 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] = 1;
				}
			}
		}
	}
	return true;
}

int main() {

	int t, n;
	scanf("%d", &t);
	while (t--) {
		
		for (int i = 1; i <= 24; i++)scanf("%d", &need[i]);
	
		memset(r, 0, sizeof r);
		scanf("%d", &n);
		while (n--) {
			int a;
			scanf("%d", &a);
			r[a + 1]++;
		}

		bool flag = false;
		for (int i = 0; i < 1001; i++) 
			if (spfa(i)) {
				printf("%d\n", i);
				flag = true;
				break;
			}
		if (!flag)printf("No Solution\n");
	}

	return 0;
}