雇佣收银员(差分约束)

雇佣收银员

Link

题意：

一家超市要每天 $24$ 小时营业，为了满足营业需求，需要雇佣一大批收银员。已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。经理为你提供了一个各个时间段收银员最小需求数量的清单 $R(0),R(1),R(2),\dots ,R(23)。$$R(0)$ 表示午夜 $00:00$ 到凌晨 $01:00$ 的最小需求数量，$R(1)$ 表示凌晨 $01:00$ 到凌晨 $02:00$ 的最小需求数量，以此类推。一共有 $N$ 个合格的申请人申请岗位，第 $i$ 个申请人可以从 $ti$ 时刻开始连续工作 $8$ 小时。收银员之间不存在替换，一定会完整地工作 $8$ 小时，收银台的数量一定足够。现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。

输入格式：

每组数据输出一个结果，每个结果占一行。如果没有满足需求的安排，输出 No Solution。

数据范围：

$0\le R(0)\le 1000,$
$0\le N\le 1000，$
$0\le t_i\le 23$

输入样例：

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
0
23
22
1
10

思路：

• 本题存在许多限制关系，即不等式方程，例如：申请人必须连续工作$8$个小时，每个时间段收银员的最小需求数量。且题目所求最少需要雇佣多少名收银员，考虑方向往差分约束方向靠。

• 题目要求的是最小需求数量，即跑最长路。

• 找不等式关系方程：由于我们需要约束申请人的$8$个小时，而每个时间段都是图中的一个点，因此本题需要用到前缀和，$S[i]$表示$1$~$i$中所有收银员的数量。

  $1:$$S[i]-S[i-1]>=0$$*$$S[i]>=S[i-1]$
  $2:$$S[i]-S[i-1]<=person[i](person[i]是i阶段申请人数量)$$*$$S[i-1]>=S[i]-person[i]$

  由于存在环即$23-24$与$1-7$会断开，所以分类讨论。

  $num[i]是指当前时间段最少需要的收银员$

  $3.1:i<=7时,S[i]+S[24]-S[16+i]>=num[i]$$*$$S[i]>=S[16+i]-S[24]+num[i]$
  $3.2:i>=8时,S[i]-S[i-8]>=num[i]$$*$$S[i]>=S[i-8]+R[i]$

  但是我们发现 $3.1$ 中出现了两个变量即$S[16+i]$与$S[24]。$ 由于最多出现$1000$个人申请收银员，所以我们可以暴力枚举$S[24]$的取值从小到大，第一个满足的即是最小的。又因为答案具有单调性，即收银员越多越满足。 所以同样可以使用二分$check。$

• 需要注意$check$部分中建图同样需要加上两个约束
  $1:add(0,24,x)$
  $2:add(24,0,-x)$
  因为我们已经将$S[24]$取常，所以$S[24]$的值也应有约束。

• 下面附上暴力枚举和二分$check$的代码：

代码1:暴力枚举+差分约束

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
const int N = 30;
const int M = 100;
int e[M],ne[M],idx,w[M];
int h[N];
int num[N];
int person[N];
int dist[N];
bool st[N];
int cnt[N];
void add(int a,int b,int c){
    
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void build(int x){
    
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=24;i++){
    
        add(i-1,i,0);
        add(i,i-1,-person[i]);
    }
    for(int i=8;i<=24;i++){
    
        add(i-8,i,num[i]);
    }
    for(int i=1;i<=7;i++){
    
        add(i+16,i,-x+num[i]);
    }
    add(0,24,x);
    add(24,0,-x);
}
bool spfa(int x){
    //判断当前的收银员人数是否足够
    build(x);//建图
    memset(st,false,sizeof st);
    memset(dist,-0x3f,sizeof dist);
    memset(cnt,0,sizeof cnt);
    queue<int>q;
    q.push(0);
    st[0]=true;
    dist[0]=0;
    while(q.size()){
    
        auto t=q.front();
        q.pop();
        st[t]=false;
        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]){
    
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return true;
}
signed main(){
    
    cin>>t;
    while(t--){
    
        memset(person,0,sizeof person);
        for(int i=1;i<=24;i++)cin>>num[i];
        cin>>n;
        for(int i=1;i<=n;i++){
    
            int x;
            cin>>x;
            x++;//0留给超级源点
            person[x]++;
        }
        bool success=false;
        for(int i=0;i<=n;i++){
    
            if(spfa(i)){
    
                success=true;
                cout<<i<<endl;
                break;
            }
        }
        if(!success)cout<<"No Solution"<<endl;
    }
    return 0;
}

代码2:二分check+差分约束

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
const int N = 30;
const int M = 100;
int e[M],ne[M],idx,w[M];
int h[N];
int num[N];
int person[N];
int dist[N];
bool st[N];
int cnt[N];
void add(int a,int b,int c){
    
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void build(int x){
    
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=24;i++){
    
        add(i-1,i,0);
        add(i,i-1,-person[i]);
    }
    for(int i=8;i<=24;i++){
    
        add(i-8,i,num[i]);
    }
    for(int i=1;i<=7;i++){
    
        add(i+16,i,-x+num[i]);
    }
    add(0,24,x);
    add(24,0,-x);
}
bool spfa(int x){
    //判断当前的收银员人数是否足够
    build(x);//建图
    memset(st,false,sizeof st);
    memset(dist,-0x3f,sizeof dist);
    memset(cnt,0,sizeof cnt);
    queue<int>q;
    q.push(0);
    st[0]=true;
    dist[0]=0;
    while(q.size()){
    
        auto t=q.front();
        q.pop();
        st[t]=false;
        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]){
    
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return true;
}
signed main(){
    
    cin>>t;
    while(t--){
    
        memset(person,0,sizeof person);
        for(int i=1;i<=24;i++)cin>>num[i];
        cin>>n;
        for(int i=1;i<=n;i++){
    
            int x;
            cin>>x;
            x++;//0留给超级源点
            person[x]++;
        }
        bool success=false;
        int l=0,r=n;
        while(l<r){
    
            int mid=l+r>>1;
            if(spfa(mid)){
    
                success=true;
                r=mid;
            }
            else l=mid+1;
        }
        if(spfa(l))success=true;
        if(success)cout<<l<<endl;
        else cout<<"No Solution"<<endl;
    }
    return 0;
}