I# 1. 题目 # 2. 题解首先，这题是考过的。原题是“计蒜客”的“蒜头君的银行卡”。当时觉得挺难的，写了个爆搜爆0了。现在想想，其实也简单。出题人写个爆搜，又写个裸的 $SPFA$ 跑负环，然后数据出大点，不就可以卡掉一堆人了吗？所以数据大点，卡掉 $SPFA$ 是必然的。 $SPFA$ 跑负环的时间复杂度是 $O(nm)$ 的，数据大点就炸了。（其实我考后也写了个 $SPFA$，结果轻松 $AC$，出题人良心发现？）正解是二分答案+差分约束。二分答案 $ans$，设 $sum[i]$ 为前 $i$ 小时总雇佣的人数。那么对于每个 $R[i]$ 我们可以列出不等式： $sum[i] – sum[i-8] \geq R[i] (i \geq 8)$ $sum[i] + sum[24] – sum[16 + i] \geq R[i] (i < 8)$ 设 $S$ 为 $sum[24]$，那么我们需要保证 $S \geq ans$，即 $S \geq ans$，这个不等式等价于 $S – sum[0] \geq ans$（因为 $sum[0]=0$）这样我们就能从 $sum[0]$ 跑最长路，判断 $S$ 是否 $\geq ans$。但是 $S$ 是我们自己设的，这个不等式不一定满足。所以我们需要枚举 $S$ 的值，再跑最长路判断是否可行。又因为 $S$ 满足单调性（如果 $S$ 满足条件则比 $S$ 大的都满足条件），所以可以二分枚举 $S$。时间复杂度 $O(24 \times 24 \times log(24 \times 1000))$ （因为 $R[i] \leq 1000$）代码： #include #define NS (25) using namespace std; templateinline void IN(_Tp&dig) { char c;dig=0; while(c=getchar(),!isdigit(c)); while(isdigit(c))dig=dig*10+c-'0',c=getchar(); } int n,R[NS],T[NS],cnt[NS],dis[NS]; bool book[NS]; queue que; struct graph { int head[NS],nxt[NS*NS],to[NS*NS],d[NS*NS],size; inline graph(){memset(head,-1,sizeof(head)),size=0;} inline void push(int a,int b,int c) { nxt[size]=head[a],to[size]=b,d[size]=c,head[a]=size++; } inline int operator [] (const int a){return to[a];} }g; bool check(int s) { g.size=0,memset(g.head,-1,sizeof(g.head)); for(int i=1;i<8;i++)g.push(i+16,i,R[i]-s); for(int i=8;i<=24;i++)g.push(i-8,i,R[i]); for(int i=1;i<=24;i++)g.push(i-1,i,0),g.push(i,i-1,-T[i]); g.push(0,24,s),g.push(24,0,-s); for(int i=0;i<=24;i++)dis[i]=-1e8,cnt[i]=0; memset(book,0,sizeof(book)),que.push(0),dis[0]=0,book[0]=1; while(!que.empty()) { int F=que.front();que.pop(),book[F]=0; if(cnt[F]>24)return 0; for(int i=g.head[F];i!=-1;i=g.nxt[i]) if(dis[g[i]]>1; if(check(mid))r=mid; else l=mid+1; } if(l>n)puts("No Solution"); else printf("%d\n",l); } return 0; } #### XZYQvQ 炒鸡辣鸡的制杖