🪴 Edwin Aze's Blog

最近文章

最近笔记

雇佣收银员

6分钟阅读

差分约束 前缀和 T4 393. 雇佣收银员 - AcWing题库 一家超市要每天 小时营业，为了满足营业需求，需要雇佣一大批收银员。

已知不同时间段需要的收银员数量不同，为了能够雇佣尽可能少的人员，从而减少成本，这家超市的经理请你来帮忙出谋划策。

经理为你提供了一个各个时间段收银员最小需求数量的清单 。

表示午夜 到凌晨 的最小需求数量， 表示凌晨 到凌晨 的最小需求数量，以此类推。

一共有 个合格的申请人申请岗位，第 个申请人可以从 时刻开始连续工作 小时。

收银员之间不存在替换，一定会完整地工作 小时，收银台的数量一定足够。

现在给定你收银员的需求清单，请你计算最少需要雇佣多少名收银员。

输入格式

第一行包含一个不超过 的整数，表示测试数据的组数。

对于每组测试数据，第一行包含 个整数，分别表示 。

第二行包含整数 。

接下来 行，每行包含一个整数 。

输出格式

每组数据输出一个结果，每个结果占一行。

如果没有满足需求的安排，输出 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

思路

雇佣最少的人员, 保证每个时段需要的收银员数量都满足。每个收银员可以工作连续的8个小时。

有个收银员应聘, 每个人都有自己的上班时间。 定义 为第 个时段可以选择的收银员数量。

设 为最终结果我们在第 时段选了多少人。显然需要让每个 都满足 。既然是多个不等式限制的问题, 考虑差分约束。

因为要求最少的人员, 也就是下界的最大值, 得出以下几个不等式条件：

  2. 条件一很好解决, 但条件二是不符合差分约束要求的形式 的。不过既然是连续区间相加, 也就是区间和, 可以采用前缀和来重构一次：设 为 的前缀和, 将 的下标从0开始。
  3. , 即 不过条件二是长度为7的区间, 在 时, 会取到前一天的时间, 因此需要分段处理。
  4. 时,
  5. 时,

这样的话条件三同样不符合形式, 但因为 有取值范围, 可以直接枚举, 最大也就 1000。 时间复杂度为 , 可以通过。

同时还需要加一个条件为 , 翻译过来就是这两个边：

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 30, M = 100;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N], cnt[N];
bool st[N];
int r[N], num[N];
int n, m;
 
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
 
void build(int c)
{
    memset(h, -1, sizeof h);
    idx = 0;
 
    for (int i = 1; i <= 24; i++)
    {
        add(i, i - 1, -num[i]);
        add(i - 1, i, 0);
    }
 
    for (int i = 8; i <= 24; i++)
        add(i - 8, i, r[i]);
    for (int i = 1; i <= 7; i++)
        add(16 + i, i, r[i] - c);
    add(0, 24, c), add(24, 0, -c);
}
 
bool spfa(int c)
{
    build(c);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0;
    while (hh != tt)
    {
        int t = q[hh++];
        if (hh == N)
            hh = 0;
 
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 25)
                    return false;
                if (!st[j])
                {
                    st[j] = true;
                    q[tt++] = j;
                    if (tt == N)
                        tt = 0;
                }
            }
        }
    }
    return true;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(num, 0, sizeof num);
        for (int i = 1; i <= 24; i++)
            cin >> r[i];
        cin >> n;
        while (n--)
        {
            int t;
            cin >> t;
            num[t + 1]++;
        }
        bool flag = true;
        for (int i = 0; i <= 1000; i++)
        {
            if (spfa(i))
            {
                flag = false;
                cout << i << endl;
                break;
            }
        }
        if (flag)
            cout << "No Solution\n";
    }
    return 0;
}

反向链接