题意：德黑兰的一家每天24小时营业的超市，需要一批出纳员来满足它的需求。超市经理雇佣你来帮他解决一个问题————超市在每天的不同时段需要不同数目的出纳员（例如，午夜只需一小批，而下午则需要很多）来为顾客提供优质服务，他希望雇佣最少数目的纳员。
超市经历已经提供一天里每一小时需要出纳员的最少数量————R(0),R(1),...,R(23）。R（0）表示从午夜到凌晨1:00所需要出纳员的最少数目；R(1)表示凌晨1：00到2：00之间需要的；等等。每一天，这些数据都是相同的。有N人申请这项工作，每个申请者i在每天24小时当中，从一个特定的时刻开始连续工作恰好8小时。定义ti(0<=ti<=23)为上面提到的开始时刻，也就是说，如果第i个申请者被录用，他（或她）将从ti时刻开始连续工作8小时。
试着编写一个程序，输入R(i),i=0，...，23，以及ti，i=1，...，N，它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目、在每一时刻可以有比对应R(i)更多的出纳员在工作
输入描述:
输入文件的第1行为一个整数T，表示输入文件中测试数据的数目(至多20个)。每个测试数据第一行为24个整数，表示R（0），R（1），...，R(23),R(i)最大可以取到1000。接下来一行是一个整数N，表示申请者的数目，0<=N<=1000。接下来有N行，每行为一个整数ti，0<=ti<=23,测试数据之间没有空行。
输出描述：
对输入文件中的每个测试数据，输出占一行，为需要雇佣的出纳员的最少数目。如果某个测试数据没有解。则输出"No Solution"。
分析：由于题目给定的是某一时刻的信息，但是试图描述的却是某一时间段的信息，所以处理的时候将时间点转化为时间段。对于每一个时间段x（每一小时作为一个时间段处理）定义出一个变量d[x]表示从1到x时间段一共雇佣了多少员工。则对于题目中所描述的数据能够较好的构图，关键还能够解决雇佣多少人的问题，而如果采用d[x]表示x时段工作的员工的人数，虽然能够列出方程但不利于问题的求解。
约定ned[x]表示x时间段至少要有多少员工在，hav[x]表示x时段有多少人申请工作，lim表示欲招的员工个数。对于题目中给定的信息构图如下：
0 <= d[x] - d[x-1] <= hav[x]; // 雇佣的人数少于申请者但不能为负数
d[x] - d[x-8] >= ned[x] // 当x>=8时，该方程成立，否则将出现负数显然不成立
d[x-8+24] - d[i] <= lim - ned[x] // 当x<8时，由于昨天的雇人可以通宵上班，因此这个约束通过反面处理
d[24] - d[0] >= lim // 最后24小时内雇佣人应该大于等于lim个人
接下来就是求解什么了，我们要得到一天最少的雇佣人数即d[24] - d[0] >= M中的M，因为M是一个变量，所以要求解M的最大值。将式子化为d[0] - d[24] <= -M，M去最大，-M取最小，即求24到0的最短路，再比较d[0]是否等于-lim。最后就是要枚举lim，因为该模型只能够判定一个lim是否能够合法，而不能够一次求出最优解，由于最多有1000人，可以采用二分查找来枚举。
代码如下：
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; // 每个节点的dis[x]表示的含义为到第x个小时时间段已经雇佣的员工数量 int N, ned[30], hav[30]; struct Edge { int v, ct, next; }e[2000]; int idx, head[30]; void insert(int a, int b, int ct) { e[idx].v = b, e[idx].ct = ct; e[idx].next = head[a]; head[a] = idx++; } void build(int lim) { idx = 0; memset(head, 0xff, sizeof (head)); for (int i = 1; i <= 24; ++i) { // d[i] - d[i-1] <= hav[i] // d[i] - d[i-1] >= 0 insert(i-1, i, hav[i]); // 雇佣的人数少于申请者 insert(i, i-1, 0); // 每个小时内雇佣的人数应该是个非负数 } for (int i = 1; i < 8; ++i) { // d[i-8+24] - d[i] <= lim-ned[i] insert(i, i-8+24, lim-ned[i]); // 由于无法直接得到从前一天的后几小时到当天前几小时的雇佣人数，所以反面求解 } for (int i = 8; i <= 24; ++i) { // d[i] - d[i-8] >= ned[i] insert(i, i-8, -ned[i]); // 前8小时内雇佣人数应该大于等于需求量 } // d[24] - d[0] >= lim 表示至少为lim个员工，这样就能够看在最好情况下能不能取到这个最小值 insert(24, 0, -lim); } #include <queue> int dis[30], cnt[30]; char vis[30]; bool spfa(int lim) { memset(dis, 0x3f, sizeof (dis)); memset(vis, 0, sizeof (vis)); memset(cnt, 0, sizeof (cnt)); queue<int>q; dis[24] = 0, vis[24] = 1, cnt[24] = 1; q.push(24); while (!q.empty()) { int v = q.front(); q.pop(); if (cnt[v] > 25) return false; vis[v] = 0; for (int i = head[v]; i != -1; i = e[i].next) { if (dis[e[i].v] > dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; if (!vis[e[i].v]) { vis[e[i].v] = 1; ++cnt[e[i].v]; q.push(e[i].v); } } } } return dis[0] == -lim; } bool bsearch(int l, int r, int &ret) { ret = -1; int mid; while (l <= r) { mid = (l + r) >> 1; // mid 表示一共能够雇佣的员工数量 build(mid); if (spfa(mid)) { ret = mid; r = mid - 1; } else { l = mid + 1; } } return ret != -1; } int main() { int T; scanf("%d", &T); while (T--) { int ret, t; memset(hav, 0, sizeof (hav)); for (int i = 1; i <= 24; ++i) { //0时刻申请将工作在第一个小时 scanf("%d", &ned[i]); } scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", &t); ++hav[t+1]; } if (bsearch(0, N, ret)) { printf("%d\n", ret); } else { puts("No Solution"); } } return 0; }