算法竞赛备考冲刺必刷题（C++） | AcWing 393 雇佣收银员
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：393. 雇佣收银员 - AcWing题库
【题目描述】
一家超市要每天24 2424小时营业，为了满足营业需求，需要雇佣一大批收银员。
已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。
经理为你提供了一个各个时间段收银员最小需求数量的清单R ( 0 ) , R ( 1 ) , R ( 2 ) , . . . , R ( 23 ) R(0),R(1),R(2),...,R(23)R(0),R(1),R(2),...,R(23)。
R ( 0 ) R(0)R(0)表示午夜00 : 00 00:0000:00到凌晨01 : 00 01:0001:00的最小需求数量，R ( 1 ) R(1)R(1)表示凌晨01 : 00 01:0001:00到凌晨02 : 00 02:0002:00的最小需求数量，以此类推。
一共有N NN个合格的申请人申请岗位，第i ii个申请人可以从t i t_iti时刻开始连续工作8 88小时。
收银员之间不存在替换，一定会完整地工作8 88小时，收银台的数量一定足够。
现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。
【输入】
第一行包含一个不超过20 2020的整数，表示测试数据的组数。
对于每组测试数据，第一行包含24 2424个整数，分别表示R ( 0 ) , R ( 1 ) , R ( 2 ) , . . . , R ( 23 ) R(0),R(1),R(2),...,R(23)R(0),R(1),R(2),...,R(23)。
第二行包含整数N NN。
接下来N NN行，每行包含一个整数t i t_iti。
【输出】
每组数据输出一个结果，每个结果占一行。
如果没有满足需求的安排，输出No Solution。
【输入样例】
1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 0 23 22 1 10【输出样例】
1【算法标签】
《AcWing 393 雇佣收银员》 #图论# #差分约束#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=30,M=100;// 最大顶点数（24小时+超级源点）和边数intn;// 申请者总数inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intr[N];// r[i]: 第i小时需要的人数intnum[N];// num[i]: 第i小时申请的人数intdist[N];// 最长距离数组intcnt[N];// 松弛计数数组，用于检测正环boolst[N];// 标记顶点是否在队列中/** * 添加有向边 * @param a 起点 * @param b 终点 * @param c 权重 */voidadd(inta,intb,intc){e[idx]=b;// 边指向的顶点w[idx]=c;// 边的权重ne[idx]=h[a];// 指向原链表头h[a]=idx++;// 更新头指针}/** * 构建差分约束图 * 根据猜测的雇佣人数c构建图 * @param c 猜测的总雇佣人数 */voidbuild(intc){// 初始化邻接表memset(h,-1,sizeof(h));idx=0;// 约束1: 0 ≤ x_i - x_{i-1} ≤ num[i]// 即: x_i ≥ x_{i-1} 且 x_i - x_{i-1} ≤ num[i]for(inti=1;i<=24;i++){// x_i ≥ x_{i-1} → x_i - x_{i-1} ≥ 0// 建边: i-1 → i，权重0add(i-1,i,0);// x_i - x_{i-1} ≤ num[i] → x_{i-1} - x_i ≥ -num[i]// 建边: i → i-1，权重 -num[i]add(i,i-1,-num[i]);}// 约束2: 对于i≥8, x_i - x_{i-8} ≥ r[i]// 建边: i-8 → i，权重 r[i]for(inti=8;i<=24;i++){add(i-8,i,r[i]);}// 约束3: 对于i≤7, x_i + c - x_{i+16} ≥ r[i]// 即: x_i - x_{i+16} ≥ r[i] - c// 建边: i+16 → i，权重 r[i] - cfor(inti=1;i<=7;i++){add(i+16,i,r[i]-c);}// 约束4: x_24 - x_0 = c// 拆分为两个不等式:// 1) x_24 - x_0 ≤ c → x_0 - x_24 ≥ -c// 2) x_24 - x_0 ≥ c → x_24 - x_0 ≥ cadd(0,24,c);// x_24 ≥ x_0 + cadd(24,0,-c);// x_0 ≥ x_24 - c}/** * SPFA算法求最长路径，并检测正环 * @param c 当前猜测的雇佣人数 * @return 存在解返回true，否则返回false */boolspfa(intc){// 构建图build(c);// 初始化memset(cnt,0,sizeof(cnt));memset(st,0,sizeof(st));memset(dist,-0x3f,sizeof(dist));// 负无穷，求最长路径dist[0]=0;// 超级源点距离为0queue<int>q;// SPFA队列q.push(0);// 起点入队st[0]=true;// 标记在队列中while(!q.empty()){intt=q.front();// 取出队首q.pop();st[t]=false;// 标记不在队列中// 遍历t的所有邻接边for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];// 邻接顶点// 松弛操作：求最长路径if(dist[j]<dist[t]+w[i]){dist[j]=dist[t]+w[i];// 更新最长距离cnt[j]=cnt[t]+1;// 松弛次数+1// 如果顶点被松弛了25次，说明存在正环if(cnt[j]>=25)// 顶点数=25（0-24）{returnfalse;// 存在正环，无解}// 如果j不在队列中，入队if(!st[j]){q.push(j);st[j]=true;}}}}returntrue;// 存在解}intmain(){intT;// 测试用例数cin>>T;while(T--){// 输入每个小时需要的人数for(inti=1;i<=24;i++){cin>>r[i];}// 输入申请者总数cin>>n;// 统计每个小时申请的人数memset(num,0,sizeof(num));for(inti=0;i<n;i++){intt;cin>>t;num[t+1]++;// 注意：时间从1开始，输入从0开始}// 二分搜索最小的雇佣人数cboolsuccess=false;for(inti=0;i<=1000;i++)// 枚举c从0到1000{if(spfa(i))// 测试雇佣i人是否可行{cout<<i<<endl;// 找到最小可行解success=true;break;}}// 如果0-1000都不可行，输出无解if(!success){puts("No Solution");}}return0;}【运行结果】
1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 0 23 22 1 10 1