算法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[16 + 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\n", 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\n", r);
else puts("No Solution");
}
return 0;
}
S24?唤醒了一些奇妙的记忆……
话说我每次重新加边,二分答案只要2ms可还行。(或许是提前判了无解的情况?)
还有就是最短路和最长路本质都是一样的,并不是因为求最小人数才用最长路(不然直接一遍最长路就行了,为什么还要枚举S24的取值呢?),我用最短路写的也可以呀。
一直不太懂这个啊。。owo
本质不一样吧?只不过是因为这题spfa用于判断是否有解,又不是用spfa求最小
当不等式组确定了,用最短检查是否存在负环和用最长检查是否存在正环来检验是否有解才是本质一样吧
弱弱的问一下,这个差分约束感觉好难,这个关系太难想了,像这一题难度在提高+,省选- 不?
就是你要考虑每个不等式只能两个未知量,所以区间和通过前缀和转化成两个变量的差就可以查分约束了
时间复杂度中不是24个点吗,怎么是26个点?
大佬,O(2028)是哪来的?
(不懂就问) tips的第二步是不是写错了?是不是最长路啊
还真是
膜拜
为什么把二分的区域变成[1, 1000] 是错误的呢?
因为可能雇佣0个吧
貌似mid举出来比n大就不行,搞不太懂为什么这样就会使图中存在正环
哦,因为s相邻差有上限bound,所以最后一个做不到大于所有的
“当 i<=7 时,s[i]+s[24]−s[24−i]>=R[i]”,这里写错了
已改正
弱弱说一句:楼主正文12行s[i]−x[i]<=x[i−1]是不是写错了,x分别改为num和s
呃貌似是的,已修正
在线建图还行
另外想说一下的是:好像不是超级原点,而是超级源点,在网络流当中有跟它相对于的点叫做超级汇点
已修正
分类讨论那里有点小错误,是
i<=7
,而不是i>=7
已修正