题目链接https://www.acwing.com/problem/content/395/涉及知识1.图论建模2.差分约束和SPFA判负环3.前缀和思路分析第一部分约束条件和建模首先本题给定了我们以下条件每个时间段收银员的最小需求记作数组r rr时刻i ii时的最小需求量便是r [ i ] r[i]r[i]N NN名收银员的开始工作时间记作数组n u m numnum时刻i ii时的总申请人数便是n u m [ i ] num[i]num[i]我们再设x i x_ixi​为对于时刻i ii我们实际选中的收银员数量。那么我们可以得到以下限制条件0 ≤ x i ≤ n u m [ i ] 0 \leq x_i \leq num[i]0≤xi​≤num[i]即某时刻i ii选定的收银员数量不能超过同时刻实际申请人数同时x i x_ixi​必须为非负整数x i − 7 x i − 6 x i − 5 x i − 4 x i − 3 x i − 2 x i − 1 x i ≥ r [ i ] x_{i-7}x_{i-6}x_{i-5}x_{i-4}x_{i-3}x_{i-2}x_{i-1}x_i \geq r[i]xi−7​xi−6​xi−5​xi−4​xi−3​xi−2​xi−1​xi​≥r[i]即从当前时刻往前倒退8小时每个时刻实际选中的收银员总量必须满足时刻i ii时的需求。题目中明确收银员一定会完整工作8小时对于上述两个不等式我们可以想到使用差分约束来确定是否存在方案并计算符合题意的答案。但是第二个不等式又有别于经典差分约束因为其为多元形式。而对于这样具有累加性的和我们又可以想到使用前缀和来进行处理。因此设s [ i ] s[i]s[i]为x xx的前缀和数组。同时还需要注意时间可能跨天需要分段处理为了给虚拟源点提供 0时间轴统一为 1 到24.故对上述两不等式进一步转化0 ≤ s [ i ] − s [ i − 1 ] ≤ n u m [ i ] 0 \leq s[i]-s[i-1] \leq num[i]0≤s[i]−s[i−1]≤num[i]{ s [ i ] − s [ i − 8 ] ≥ r [ i ] , 8 ≤ i ≤ 24 s [ i ] s [ 24 ] − s [ 16 i ] ≥ r [ i ] , 1 ≤ i ≤ 7 \begin{cases} s[i]-s[i-8] \geq r[i],8 \leq i \leq24\\ s[i]s[24]-s[16i] \geq r[i],1 \leq i \leq 7 \end{cases}{s[i]−s[i−8]≥r[i],8≤i≤24s[i]s[24]−s[16i]≥r[i],1≤i≤7​到这里很明显就可以使用差分约束了。而对于此题需要求最小值则需要跑最长路需要将不等式统一转化为形如x i ≥ x j k x_i \geq x_j kxi​≥xj​k的形式。最后通过化简和整理可得最终我们需要的约束条件s [ i ] ≥ s [ i − 1 ] s[i] \geq s[i-1]s[i]≥s[i−1]s [ i − 1 ] ≥ s [ i ] − n u m [ i ] s[i-1]\geq s[i]-num[i]s[i−1]≥s[i]−num[i]{ s [ i ] ≥ s [ i − 8 ] r [ i ] , 8 ≤ i ≤ 24 s [ i ] ≥ s [ 16 i ] − s [ 24 ] r [ i ] , 1 ≤ i ≤ 7 \begin{cases} s[i] \geq s[i-8]r[i],8 \leq i \leq24\\ s[i] \geq s[16i]-s[24]r[i],1 \leq i \leq 7 \end{cases}{s[i]≥s[i−8]r[i],8≤i≤24s[i]≥s[16i]−s[24]r[i],1≤i≤7​根据s ss的含义不难发现最终我们需要求的“最少的收银员数量”可以等价于s [ 24 ] s[24]s[24]而此题的数据范围保证N ≤ 1000 N \leq 1000N≤1000故我们可以直接枚举0 00到n nn作为常量c cc将其传入 SPFA 算法来判断是否符合题意由于是递增枚举只要我们找到第一个符合题意的c cc便可以确定答案。设a d d ( a , b , c ) add(a,b,c)add(a,b,c)为在点a aa和b bb之间建立一条边权为c cc的边 根据得到的不等式可以知道需要执行以下操作建图a d d ( i − 1 , i , 0 ) , 1 ≤ i ≤ 24 add(i-1,i,0),1 \leq i \leq 24add(i−1,i,0),1≤i≤24a d d ( i , i − 1 , − n u m [ i ] ) , 1 ≤ i ≤ 24 add(i,i-1,-num[i]),1 \leq i \leq24add(i,i−1,−num[i]),1≤i≤24a d d ( i − 8 , i , r [ i ] ) , 8 ≤ i ≤ 24 add(i-8,i,r[i]),8 \leq i \leq 24add(i−8,i,r[i]),8≤i≤24a d d ( 16 i , i , − c r [ i ] ) , 1 ≤ i ≤ 7 add(16i,i,-cr[i]),1 \leq i \leq 7add(16i,i,−cr[i]),1≤i≤7第二部分程序框架逻辑对于每一组测试数据在初始化各类数组和输入数据后我们直接从 0 到n nn枚举常量c cc作为s [ 24 ] s[24]s[24]对每一个常量c cc跑 SPFA。在每一次跑 SPFA 时都利用当前常量c cc重新建一遍图再通过最长路判读是否存在负环如果存在负环则说明当前常量c cc不符合题意如果不存在负环则当前即为答案。即可输出答案、跳出循环。AC代码#includeiostream#includecstdio#includealgorithm#includecstring#includequeueusingnamespacestd;constintN30,M100;intT;intn;inte[M],ne[M],w[M],h[N],idx;intst[N],dis[N],cnt[N];intr[N],num[N];voidadd(inta,intb,intc){w[idx]c;e[idx]b;ne[idx]h[a];h[a]idx;return;}voidbuild(intc){memset(h,-1,sizeofh);idx0;for(inti1;i24;i)add(i-1,i,0);for(inti1;i24;i)add(i,i-1,-num[i]);for(inti8;i24;i)add(i-8,i,r[i]);for(inti1;i7;i)add(i16,i,-cr[i]);add(0,24,c),add(24,0,-c);return;}boolspfa(intc){build(c);//建边memset(dis,-0x3f3f3f3f,sizeofdis);memset(cnt,0,sizeofcnt);memset(st,0,sizeofst);queueintq;dis[0]0;st[0]true;q.push(0);while(!q.empty()){intnowq.front();q.pop();st[now]false;for(intih[now];i!-1;ine[i]){intje[i];if(dis[j]dis[now]w[i]){dis[j]dis[now]w[i];cnt[j]cnt[now]1;if(cnt[j]24)returnfalse;if(!st[j]){st[j]true;q.push(j);}}}}returntrue;}intmain(){scanf(%d,T);while(T--){memset(num,0,sizeofnum);memset(r,0,sizeofr);for(inti1;i24;i)scanf(%d,r[i]);scanf(%d,n);for(inti1;in;i){intt;scanf(%d,t);num[t];//上面输入时是1到24}boolsuccessfalse;for(inti0;in;i){if(spfa(i)){printf(%d\n,i);successtrue;break;}}if(!success)printf(No Solution\n);}return0;}