Hire cashier (differential constraint)

Hire a cashier

Link

The question ：

A supermarket needs to $24$ Hours open , In order to meet business needs , Need to hire a large number of cashiers . It is known that the number of cashiers required in different time periods is different , In order to be able to hire as few people as possible , To reduce costs , The manager of this supermarket asked you to help with some advice . The manager provides you with a list of the minimum number of cashiers required in each time period $R(0),R(1),R(2),\dots ,R(23).$$R(0)$ It means midnight $00:00$ Into the morning $01:00$ Minimum required quantity of ,$R(1)$ Morning Express $01:00$ Into the morning $02:00$ Minimum required quantity of , And so on . Altogether $N$ A qualified applicant applies for a position , The first $i$ Applicants can choose from $ti$ Start working continuously all the time $8$ Hours . There is no replacement between cashiers , Will work completely $8$ Hours , There must be enough cash registers . Now give your cashier's demand list , Please calculate the minimum number of cashiers you need to hire .

Input format ：

Each group of data outputs a result , Each result takes up one line . If there is no arrangement to meet the needs , Output No Solution.

Data range ：

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

sample input ：

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

Ideas ：

• There are many restrictions on this topic , Inequality equation , for example ： Applicants must work continuously $8$ Hours , Cashier's for each time period Minimum required quantity . And the minimum number of cashiers required by the question , Consider the direction to the direction of the difference constraint .

• The topic requires the minimum required quantity , namely The longest run .

• Find the inequality relation equation ： Because we need to restrain the applicant $8$ Hours , Each time period is a point in the graph , Therefore, the prefix and ,$S[i]$ Express $1$~$i$ Number of all cashiers in .

  $1:$$S[i]-S[i-1]>=0$$*$$S[i]>=S[i-1]$
  $2:$$S[i]-S[i-1]<=person[i](person[i]yesirankparagraphShenpleasepeopleCountThe\; amount)$$*$$S[i-1]>=S[i]-person[i]$

  Because there is a ring, that is $23-24$ And $1-7$ Will disconnect , So classified discussion .

  $num[i]yesfingerWhenfrontwhenbetweenparagraphmostLessNeed\; to\; bewantOfclosedsilvermember$

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

  But we found that $3.1$ There are two variables in $S[16+i]$ And $S[24].$ Because at most $1000$ Individual application cashier , So we can enumerate violence $S[24]$ From small to large , The first satisfaction is the smallest . And because the answer is monotonous , That is, the more cashiers, the more satisfied . So you can also use Two points $check.$

• We need to pay attention to $check$ Two constraints also need to be added to some drawings under construction
  $1:add(0,24,x)$
  $2:add(24,0,-x)$
  Because we already have $S[24]$ Take regular , therefore $S[24]$ The value of should also be constrained .

• The violence enumeration and dichotomy are attached below $check$ Code for ：

Code 1: Violence enumeration + Difference constraint

#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){
    // Judge whether the current number of cashiers is sufficient 
    build(x);// Drawing 
    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 Leave it to the super source 
            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;
}

Code 2: Two points check+ Difference constraint

#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){
    // Judge whether the current number of cashiers is sufficient 
    build(x);// Drawing 
    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 Leave it to the super source 
            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;
}