AcWing 393. 雇佣收银员 -数据天堂

AcWing 393. 雇佣收银员

# windos 2024-04-03 09:12 0 14 来源：数据天堂

原题链接

考察:差分约束+二分+前缀和

思路:

某个区间有多少个,考虑前缀和.

那么: s[i] - s[i-1] >= 0 , s[i] - s[i-1] 表示第i小时雇佣的人,s[i] - s[i-1] <= sum[i] sum[i]表示可以在i时刻开始工作的人数.

注意r[i]表示第i小时需要的人数,第i小时可以被i-7~i覆盖. 所以 s[i] - s[i-8] >= r[i].

如果i>=8 可以是上面的式子,但是当i<8 式子就变成 s[i] +s[24] - s[i+16] >= r[i]

最后一个不等式有三个变量,不能简单的差分约束.一个简单的方法就是枚举s[24], 这明显有单调性,直接二分即可.

注意,为了在不等式里凸显s[24] = mid 需要 s[24] <=mid && s[24] >=mid;

 1 #include <iostream>  2 #include <cstring> 3 #include <stack> 4 using namespace std; 5 const int N = 30,M = 120; 6 int r[N],n,sum[N],idx,h[N],cnt[N],dist[N]; 7 bool st[N]; 8 struct Road{ 9 int fr,to,ne,w;10 }road[M];11 void add(int a,int b,int c)12 {13 road[idx].w = c,road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;14 }15 bool spfa(int m)16 {17 idx = 0;18 memset(h,-1,sizeof h); memset(cnt,0,sizeof cnt);19 memset(st,0,sizeof st); memset(dist,0,sizeof dist);20 for(int i=1;i<=24;i++) dist[i] = -0x3f3f3f3f;21 for(int i=8;i<=24;i++) add(i-8,i,r[i]);22 for(int i=1;i<=24;i++) add(i-1,i,0);23 for(int i=1;i<=24;i++) add(i,i-1,-sum[i]);24 for(int i=1;i<8;i++) add(16+i,i,r[i]-m);25 add(0,24,m); add(24,0,-m);26 stack<int> q;27 q.push(0); st[0] = 1;28 while(q.size())29  {30 int u = q.top();31  q.pop();32 st[u] =0;33 for(int i=h[u];~i;i=road[i].ne)34  {35 int v = road[i].to;36 if(dist[v]<dist[u]+road[i].w)37  {38 dist[v] = dist[u]+road[i].w;39 cnt[v] = cnt[u]+1;40 if(cnt[v]>=25) return 0; 41 if(!st[v]) q.push(v),st[v] = 1;42  }43  }44  }45 return 1;46 }47 int main()48 {49 // freopen("in.txt","r",stdin);50 int T;51 scanf("%d",&T);52 while(T--)53  {54 memset(sum,0,sizeof sum);55 for(int i=1;i<=24;i++) scanf("%d",&r[i]);56 scanf("%d",&n);57 for(int i=1;i<=n;i++)58  {59 int x; scanf("%d",&x);60 sum[x+1]++;61  }62 int l = 0,r = n+1;63 while(l<r)64  {65 int mid = l+r>>1;66 if(spfa(mid)) r = mid;67 else l = mid+1;68  }69 if(r==n+1) puts("No Solution");70 else printf("%d\n",r);71  }72 return 0;73 }