跳转至

雇佣收银员

原题链接

题目描述

一家超市要每天 \(24\) 小时营业，为了满足营业需求，需要雇佣一大批收银员。

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

经理为你提供了一个各个时间段收银员最小需求数量的清单 \(R(0),R(1),R(2),…,R(23)\)。

\(R(0)\) 表示午夜 \(00:00\) 到凌晨 \(01:00\) 的最小需求数量，\(R(1)\) 表示凌晨 \(01:00\) 到凌晨 \(02:00\) 的最小需求数量，以此类推。

一共有 \(N\) 个合格的申请人申请岗位，第 \(i\) 个申请人可以从 \(t_i\) 时刻开始连续工作 \(8\) 小时。

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

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

差分约束

要求最小值，我们用最长路来求解。

我们设 \(num[i]\) 为 \(i\) 时刻有多少人申请上岗，\(r[i]\) 为 \(i\) 时刻的需求人数，\(x[i]\) 为 \(i\) 时刻为有多少人实际上岗。其中 \(s\) 为 \(x\) 的前缀和。

那么可以得到以下差分约束：

  • \(s[i]\ge s[i-1]\Rightarrow s[i]\ge s[i-1]\)
  • \(s[i]-s[i-1]\le num[i]\Rightarrow s[i-1]\ge s[i]-num[i]\)
  • \(s[i]-s[i-8]\ge r[i]\Rightarrow s[i]\ge s[i-8]+r[i]~(i\ge 8)\)
  • \(s[i]+s[24]-s[16+i]\ge r[i]\Rightarrow s[i]\ge s[16+i]-s[24]+r[i]~(i\le 7)\)

注意到第四个条件中有三个变量。我们可以在 \([0,1000]\) 枚举 \(s[24]\)。

假设枚举到的 \(s[24]=c\)，那么约束条件为：

  1. \(s[24]\ge c\Rightarrow s[24]\ge s[0]+c\)
  2. \(s[24]\le c\Rightarrow s[0]\ge s[24]-c\)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;

const int N = 30, M = 100;

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N], r[N], num[N];
bool st[N];

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;

    add(0, 24, c);
    add(24, 0, -c);
    for (int i = 1; i <= 24; i++) {
        add(i - 1, i, 0);
        add(i, i - 1, -num[i]);
    }
    for (int i = 1; i <= 7; i++) add(i + 16, i, r[i] - c);
    for (int i = 8; i <= 24; i++) add(i - 8, i, r[i]);
}

bool spfa(int c) {
    build(c);

    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, false, sizeof st);

    queue<int> q;
    q.push(0);
    st[0] = true;
    dist[0] = 0;

    while (q.size()) {
        int u = q.front();
        q.pop();

        st[u] = false;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= 25) return false;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

void solve() {
    memset(num, 0, sizeof num);
    for (int i = 1; i <= 24; i++) cin >> r[i];
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        num[x + 1]++;
    }

    bool ok = false;
    for (int i = 0; i <= 1000; i++)
        if (spfa(i)) {
            ok = true;
            cout << i << endl;
            break;
        }

    if (!ok) cout << "No Solution" << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
回到页面顶部