标签：表示 区间 open ++ 链接 names 就是 solution 前缀和
原题链接
考察:差分约束+二分+前缀和
思路:
某个区间有多少个,考虑前缀和.
那么: s[i] - s[i-1] >= 0 , s[i] - s[i-1] 表示第i小时雇佣的人,s[i] - s[i-1]
注意r[i]表示第i小时需要的人数,第i小时可以被i-7~i覆盖. 所以 s[i] - s[i-8] >= r[i].
如果i>=8 可以是上面的式子,但是当i= r[i]
最后一个不等式有三个变量,不能简单的差分约束.一个简单的方法就是枚举s[24], 这明显有单调性,直接二分即可.
注意,为了在不等式里凸显s[24] = mid 需要 s[24] =mid;
1 #include 2 #include 3 #include 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;i24;i++) dist[i] = -0x3f3f3f3f;
21 for(int i=8;i24;i++) add(i-8,i,r[i]);
22 for(int i=1;i24;i++) add(i-1,i,0);
23 for(int i=1;i24;i++) add(i,i-1,-sum[i]);
24 for(int i=1;i8;i++) add(16+i,i,r[i]-m);
25 add(0,24,m); add(24,0,-m);
26 stackint> 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]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;i24;i++) scanf("%d",&r[i]);
56 scanf("%d",&n);
57 for(int i=1;i)
58 {
59 int x; scanf("%d",&x);
60 sum[x+1]++;
61 }
62 int l = 0,r = n+1;
63 while(lr)
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 }
AcWing 393. 雇佣收银员
标签：表示 区间 open ++ 链接 names 就是 solution 前缀和
原文地址：https://www.cnblogs.com/newblg/p/14746979.html