自动搬运

查看原文

来自洛谷，原作者为

	MattL 卧室奶龙

搬运于2025-08-24 23:02:45，当前版本为作者最后更新于2024-11-19 08:10:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

标签：二分、差分约束、图论建模、负环

建议评紫。这种类似的题几乎都是紫。

建议加强数据。才一个点，而且这个数据范围完全可以大很多

---

题意描述地很清晰，除了格式有点丑，理解应该没有困难。

观察题目，某个时间点的人数要大于等于要求人数。这需要用到不等式，容易想到差分约束。

考虑如何建图。差分约束经典套路，先用前缀和表示。这样就能变成两个数的差而非一堆数的和。

用 $x_i$ 表示第 $i$ 小时开始工作的人数，$s_i=\sum_{j=0}^i x_j$，可以写出不等式如：

$$x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8\geq R_8$$ $$s_8-s_0\geq R_8$$

但是注意到 0 到 7 点很难处理，因为时间点形成一个环。不同于网络上大多数的做法断环为链，这里采用另一种方法。（断环为链简单介绍一下。就是把环复制两遍，这样尾接头的部分可以保证连续。）

如：

$$x_{20}+x_{21}+x_{22}+x_{23}+x_0+x_1+x_2+x_3\geq R_3 $$$$s_{23}-s_{19}+s_3\geq R_3$$

注意到，$s_{23}=ans$，即总雇佣人数。但我们求解答案的时候肯定无法得知答案，怎么办呢？

容易想到二分答案。二分出一个 $mid$，此时可以写出不等式：

$$mid-s_{19}+s_3\geq R_3$$

由于总数是 $mid$，故还有条件：

$$s_{23}=mid$$

即：

$$mid\leq s_{23}\leq mid$$

同时，要使这个问题成立，使解有意义，还需满足一下不等式：

$$0\leq s_i-s_{i-1}\leq a_i$$

（$a_i$ 表示第 $i$ 个小时开始工作的有 $a_i$ 个人应聘）

以上不等式均为两数之差（一个数的补足 0 个数的前缀和），按不等式建图差分约束即可。若跑出来没有负环则二分的这个答案成立。

实现的时候注意用到的 0 个数的前缀和是 $s_{-1}$，会爆下标，故所有下标 $+1$。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ls (now<<1)
#define rs (now<<1|1)
#define LL long long
#define f(i,n) for(int i=1;i<=n;i++)
#define f_(i,n) for(int i=n;i>=1;i--)
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define ff_(i,a,b) for(int i=a;i>=b;i--)
#define pi pair<int,int> 
#define pb push_back
#define vi vector<int>
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define fs(i,s) for(int i=0;i<s.size();i++)
#define re return
#define con continue
#define bre break
#define mkp make_pair

const int N=25;
int r[N],a[N];
int n=25,m,dis[N],cnt[N];
vector<pi> to[N];
bool vis[N];
bool check(int k){
	ff(i,0,24)to[i].clear();
	f(i,24)to[i-1].pb(mkp(i,a[i-1])),to[i].pb(mkp(i-1,0));
	ff(i,0,6)to[i+1].pb(mkp(i+24-8+1,k-r[i])); 
	ff(i,7,23)to[i+1].pb(mkp(i-8+1,-r[i]));
	to[0].pb(mkp(24,k));
	to[24].pb(mkp(0,-k));
	queue<int> q;
	q.push(0);
	memset(dis,63,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[0]=0;cnt[0]=1;vis[0]=1;
	while(!q.empty()){//spfa
		int k=q.front();q.pop();vis[k]=0;
		for(auto i:to[k]){
			if(dis[i.first]>dis[k]+i.second){
				dis[i.first]=dis[k]+i.second;
				if(!vis[i.first]){
					cnt[i.first]++;vis[i.first]=1;
					q.push(i.first);
					if(cnt[i.first]>=n+1){
						return 0;//有负环则不成立
					}
				}
			}
		}
	}return 1;
}
void solve(){
	ff(i,0,23)cin>>r[i],a[i]=0;
	int m,tmp;
	cin>>m;
	f(i,m){
		cin>>tmp;
		a[tmp]++;
	}int l=0,r=m+1;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}if(l==m+1)cout<<"No Solution\n";
	else cout<<l<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
    	solve();
	}
    return 0;
}