[HOJ 272] 出納員的僱用

作法：

考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=50 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
int cnt[maxn],inq[maxn],d[maxn] ;
bool Bellman(int st)
{
    memset(cnt,0,sizeof(cnt)) ;
    memset(inq,0,sizeof(inq)) ;
    fill(d,d+maxn,1e9) ;
    queue<int> q ;
    d[st]=0 ; q.push(st) ; inq[st]=1 ;
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ; inq[u]=0 ;
        if(++cnt[u]==maxn) return 1 ;
        for(auto i : v[u]) if(d[i.to]>d[u]+i.dis)
        {
            d[i.to]=d[u]+i.dis ;
            if(!inq[i.to]) q.push(i.to) ;
            inq[i.to]=1 ;
        }
    }
    return 0 ;
}
 
int num[maxn],need[maxn] ;
bool check(int x)
{
    for(int i=0;i<maxn;i++) v[i].clear() ;
    for(int i=0;i<8;i++)
        v[24+i].push_back((P){i,x}) ,
        v[i].push_back((P){24+i,-x}) ;
    for(int i=1;i<=24;i++) v[i].push_back((P){i-1,num[i]}) ;
    for(int i=8;i<=31;i++) v[i-8].push_back((P){i,-need[(i-1)%24+1]}) ;
    for(int i=0;i<32;i++) v[32].push_back((P){i,0}) ;
    return !Bellman(32) ;
}
 
main()
{
    for(int i=1;i<=24;i++) scanf("%d",&need[i]) ;
    int k ; scanf("%d",&k) ;
    for(int i=1;i<=k;i++){int x ; scanf("%d",&x) ; num[x+1]++ ;}
    int l=-1 , r=k+1 ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    if(l==k) printf("No Solution\n") ;
    else printf("%d\n",r) ;
}