题解：P10941 Cashier Employment

MattL · 2024-11-19 08:10:40 · 题解

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

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

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

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

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

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

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

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

如：

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

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

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

即：

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

（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;
}