算法1： 差分约束 + 枚举 O(Tn2028)
由于牵扯到 ([i - 8 + 1, i]) 这段区间的和的约束，所以用前缀和更好表达一些。
设 (num[i])表示 (i) 时刻有多少人申请上岗， (x[i]) 为 (i) 时刻实际上岗的人数 ，(s) 为 (x) 的前缀和数组。
则应该满足的约束条件是：
-
上岗人数不能负数，即 (s[i] - s[i - 1] >= 0)
-
实际上岗人数不能超过申请人数，即 (s[i] - s[i - 1] <= num[i])
-
(i) 时刻所在人数，即 ([i - 7, i]) 区间内的上岗人数要大于等于最小需求 (R)
由于存在环，即 (23) 到 (24)，再到 (0) 时刻，所以要分类讨论：
- 当 (i >= 8) 时，(s[i] - s[i - 8] >= R[i])
- 当 (i <= 7) 时，(s[i] + s[24] - s[24 - i] >= R[i])
显然这是一个明显的差分约束问题，由于求最小人数，所以用最长路转化：
- (s[i] >= s[i - 1]) 即 (add(i - 1, i, 0))
- (s[i] - num[i] <= s[i - 1]) 即 (add(i, i - 1, -num[i]))
- (s[i - 8] + R[i] <= s[i]) 即 (add(i - 8, i, R[i]))
- (s[16 + i] + R[i] - s[24] <= s[i])，不会连边了hhhh
最后一种约束关系我们不会连边的原因无非是出现了三个变量，但我们可以发现：
- 所有最后一种约束关系都有 (s[24]) 变量，其实这个东西就是我们求的答案，所以我们可以枚举 (s[24]) 的值，把它变成常量就行啦！然后就可以 (add(16 + i, i, R[i] - s[24]))
(Tips：)
-
关于建图，其实可以在线建图，不用僵化建边了嘿嘿。
-
发现 (0) 肯定所有点，所以不用创造超级源点了，只需从 (0) 点出发跑最短路即可。
-
不要忘了 $s[24] = $ 我们枚举的数 (c)（要严格等于，实现是 大于等于 + 小于等于）：
- (s[24] <= c) 即 (add(24, 0, -c))
- (s[24] >= c) 即 (add(0, 24, c))
时间复杂度
这个题中的点数 $ <= 26$，边数 $ <= 26 * 3 = 78$，
所以时间复杂度 (O(Tn2028))，足以 (AC)
(5ms) 可还行
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;
int n, ans, cnt[N], dis[N], R[N], num[N];
int tt, q[N];
bool st[N];
/*
最长路
0 <= Si - S(i - 1)
*/
//把边 (u, v, w) 松弛
bool inline upd(int u, int v, int w) {
if(dis[u] + w > dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= 25) return false;
if(!st[v]) q[++tt] = v, st[v] = true;
}
return true;
}
// 返回是否存在可行解
bool spfa() {
memset(dis, -0x3f, sizeof dis);
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
// 数组模拟栈 更容易找到环
tt = 0;
q[++tt] = 0; dis[0] = 0;
while(tt) {
int u = q[tt--];
st[u] = false;
// 严格保证 s[24] = ans
if(u == 0 && !upd(0, 24, ans)) return false;
if(u == 24 && !upd(24, 0, -ans)) return false;
// s[i] - s[i - 1] >= 0
if(u < 24 && !upd(u, u + 1, 0)) return false;
// s[i] - s[i - 1] <= num[i]
if(u > 0 && !upd(u, u - 1, -num[u])) return false;
//s[i] - s[i - 8] >= R[i]
if(u <= 16 && !upd(u, u + 8, R[u + 8])) return false;
// s[i] + s[24] - s[24 - i] >= R[i]
if(u >= 17 && !upd(u, u - 16, R[u - 16] - ans)) return false;
}
return true;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
memset(num, 0, sizeof num);
for (int i = 1; i < N; i++) scanf("%d", R + i);
scanf("%d", &n);
for (int i = 1, x; i <= n; i++)
scanf("%d", &x), x++, num[x]++;
bool ok = false;
// 枚举 s24, s24 就是 答案
for (ans = 0; ans <= n; ans++) {
if(spfa()) {
printf("%d
", ans);
ok = true;
break;
}
}
if(!ok) puts("No Solution");
}
return 0;
}
算法2： 差分约束 + 二分 O(T2028logN)
显然，答案具有单调性（若允许上岗的人越多，越容易满足条件）。
所以可以二分答案 (LOL)。
(3ms) 可还行
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;
int n, cnt[N], dis[N], R[N], num[N];
int tt, q[N];
bool st[N];
/*
最长路
0 <= Si - S(i - 1)
*/
//把边 (u, v, w) 松弛
bool inline upd(int u, int v, int w) {
if(dis[u] + w > dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= 25) return false;
if(!st[v]) q[++tt] = v, st[v] = true;
}
return true;
}
// 返回是否存在可行解
bool spfa(int s24) {
memset(dis, -0x3f, sizeof dis);
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
// 数组模拟栈 更容易找到环
tt = 0;
q[++tt] = 0; dis[0] = 0;
while(tt) {
int u = q[tt--];
st[u] = false;
// 严格保证 s[24] = s24
if(u == 0 && !upd(0, 24, s24)) return false;
if(u == 24 && !upd(24, 0, -s24)) return false;
// s[i] - s[i - 1] >= 0
if(u < 24 && !upd(u, u + 1, 0)) return false;
// s[i] - s[i - 1] <= num[i]
if(u > 0 && !upd(u, u - 1, -num[u])) return false;
//s[i] - s[i - 8] >= R[i]
if(u <= 16 && !upd(u, u + 8, R[u + 8])) return false;
// s[i] + s[24] - s[24 - i] >= R[i]
if(u >= 17 && !upd(u, u - 16, R[u - 16] - s24)) return false;
}
return true;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
memset(num, 0, sizeof num);
for (int i = 1; i < N; i++) scanf("%d", R + i);
scanf("%d", &n);
for (int i = 1, x; i <= n; i++)
scanf("%d", &x), x++, num[x]++;
int l = 0, r = n;
while(l < r) {
int mid = (l + r) >> 1;
if(spfa(mid)) r = mid;
else l = mid + 1;
}
if(spfa(r)) printf("%d
", r);
else puts("No Solution");
}
return 0;
}