aytony

求古寻论，散虑逍遥。

0%

题解 POJ1275 Cashier Employment

发表于 更新于 分类于 ，
题解 POJ1275 Cashier Employment

1275 -- Cashier Employment - POJ
1420 Cashier Employment – ZOJ
U133833 店主的困惑 (Puzzlement of Merchant) - 洛谷 计算机科学教育新生态

其中 POJ 和洛谷数据较为全面，建议使用 POJ 或洛谷提交。数据强度 洛谷 > POJ > ZOJ 。

本题解以洛谷平台数据为准。

题目大意

有 \(T\) 组数据。店主要雇佣一部分店员。对于一天中的第 \(i\) 小时，店主需要 \(D_i\) 个店员工作。对于 \(n\) 个店员，每个店员会从 \(t_i\) 的时间内开始工作，连续工作 \(8\) 个小时。请问最少雇佣的店员的数量。

其中 \(1 \leqslant T \leqslant 1000\) , \(0 \leqslant D_i \leqslant 1000\) , \(0 \leqslant n \leqslant 10000\) , \(1 \leqslant t_i \leqslant 24\) 。

算法选择

可以轻易构建出不等式，并求极值。选择差分约束。关于差分约束，见下。

算法 差分约束 | 散虑の春雨寻风

算法分析

对于原题中的 \(t_i\) ，统计成为 \(P_i\) ，其中 \(P_i\) 代表第 \(i\) 个小时来应聘的人数。设第 \(i\) 个小时录用的人数为 \(A_i\) 。

接下来，对 \(P_i\) , \(A_i\) 和 \(D_i\) 进行分析，并推导约束条件。

首先，对于每个时刻，录取的人数应小于等于前来应聘的人数。故有 \(A_i \leqslant P_i\) 。

其次，对于每个时刻，工作的人数应大于等于店长的需求。即对于第 \(i\) 个小时，此小时及前 \(7\) 个小时录用的人员之和应该大于等于 \(D_i\) 。假设正在分析第 \(i\) 个小时。则当 \(i \geqslant 8\) 时，只要

\[A_{i-7} + A_{i-6} + \cdots + A_i \geqslant P_i\]

即可满足。当 \(1 \leqslant i \leqslant 7\) 时，只要

\[A_1 + A_2 + \cdots + A_i + A_{i +17} +A_{i + 18} + \cdots + A_{24} \geqslant P_i\]

时，即可满足。

为化为差分约束所需形式，设 \(S_i\) = \(A_1 + A_2 + \cdots + A_i\) 且 \(S_0 = 0\) ，则上面的算式可总结为

\[\left\{ \begin{aligned}S_{i -1} \ - S_i&\geqslant -P_i &(1 \leqslant i \leqslant 24) \\ S_i \ - S_{i-1}&\geqslant 0 &(1 \leqslant i \leqslant 24) \\ S_i \ - S_{i-8}&\geqslant D_i &(8 \leqslant i \leqslant 24) \\ S_i \ - S_{i + 16}&\geqslant D_i \ - S_{24} &(1 \leqslant i \leqslant 7)\end{aligned}\right.\]

但是考虑到 \(S_{24}\) 为未知量，考虑枚举 \(S_{24}\) 并对每个枚举进行差分约束。假设目前枚举至 \(cur\) ，则上方程组的最后一个方程可以转化为

\[S_i \ - S_{i + 16} \geqslant D_i \ - cur\]

但是此方程与原方程组的最后一个方程不能够等价替代。考虑根据此方程计算出的 \(S_{24}\) 与枚举的 \(cur\) 的关系，不妨直接增加差分约束条件 \(S_{24} = cur\) ，这样若是在枚举 \(cur\) 时存在可行解，则差分约束系统一定会给出一可行解；若是对于 \(cur\) 不存在可行解，则一定会有不等式互相矛盾，即图中有正环存在。根据此性质，我们可以在 \(0\) 到 \(n\) 范围内二分 \(cur\) 。

至此，所有的约束条件已经推导出，在此列举出来。

\[\left\{ \begin{aligned}S_{i -1} \ - S_i&\geqslant -P_i &(1 \leqslant i \leqslant 24) \\ S_i \ - S_{i-1}&\geqslant 0 &(1 \leqslant i \leqslant 24) \\ S_i \ - S_{i-8}&\geqslant D_i &(8 \leqslant i \leqslant 24) \\ S_i \ - S_{i + 16}&\geqslant D_i \ - cur &(1 \leqslant i \leqslant 7) \\ S_{24} &= cur\end{aligned}\right.\]

代码实现

测试点用时最长约 700ms 。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

const int NMAX = 25;
const int MMAX = 128;
const int NINF = -0x7f7f7f7f;
const int INF = 0x7f7f7f7f;

struct edge
{
    int from, to, w;
    edge *nxt;
};

/* --- VARIABLES --- */
// global
int n, P[NMAX], D[NMAX];
// graph
edge edges[MMAX], *head[NMAX];
int cnt = 0;

/* --- FUNCTIONS --- */
// graph
inline void addline(int from, int to, int w)
{
    edges[cnt] = (edge){from, to, w, head[from]};
    head[from] = &edges[cnt++];
}

// SPFA
int SPFA()
{
    int dis[NMAX], count[NMAX] = {0};
    bool inq[NMAX] = {0};
    queue<int> que;
    memset(dis, NINF, sizeof(dis));
    dis[0] = 0;
    que.push(0), inq[0] = true, count[0]++;

    while (!que.empty())
    {
        int fnt = que.front();
        que.pop(), inq[fnt] = false;
        for (edge *p = head[fnt]; p; p = p->nxt)
            if (dis[p->to] < dis[fnt] + p->w)
            {
                dis[p->to] = dis[fnt] + p->w;
                if (!inq[p->to])
                    que.push(p->to), inq[p->to] = true, count[p->to]++;
                if (count[p->to] > NMAX)
                    return false;
            }
    }
    return true;
}

// main
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(P, 0, sizeof(P));
        for (register int i = 1; i <= 24; i++)
            scanf("%d", &D[i]);
        scanf("%d", &n);
        for (register int i = 1, tmp; i <= n; i++)
        {
            scanf("%d", &tmp);
            P[tmp + 1]++;
        }

        int L = 0, R = n, ans = -1;
        while (L <= R)
        {
            int cur = (L + R) >> 1;
            memset(head, 0, sizeof(head)), cnt = 0;

            for (register int i = 1; i <= 24; i++)
                addline(i - 1, i, 0), addline(i, i - 1, -P[i]);
            for (register int i = 1; i <= 7; i++)
                addline(i + 16, i, D[i] - cur);
            for (register int i = 8; i <= 24; i++)
                addline(i - 8, i, D[i]);
            addline(0, 24, cur), addline(24, 0, -cur);

            if (SPFA())
                R = cur - 1, ans = cur;
            else
                L = cur + 1;
        }

        if (~ans)
            printf("%d\n", ans);
        else
            puts("No Solution");
    }

    system("pause");
    return 0;
}

参考资料

  1. 冯威《数与图的完美结合——浅析差分约束系统》
  2. 1755 【差分约束】Cashier Employment(出纳员的雇佣) - 百度文库