题解：P10941 Cashier Employment

题意：

现在有一家每天

24

小时营业的超市,需要一批出纳员。

然后需要的话它提供了一个需求,就是说你在从

0

点开始到

23

点。

你在每一个就是这样的一个时间点的话他都会给出一个所需要的最小的出纳员的数量。

正解：

首先，用

r_i

表示：第

i

时刻所需要的最少人数。

好，然后我们怎么把这个人跟申请者去建立联系呢？

我们可以发现，如果说你招

1

个人，这个人是可以工作

2 \sim 8

个小时的。

所以如果说我希望在第

2

个小时这边工作那么，它其实可以是

i

小时站岗，也可以是

i - 1

小时上岗，也可以是

i - 2

一直往前，是一直可以到

i - 7

，那么它在这

8

个小时开始工作的出纳员，最终在第

2

个小时是不是都会工作？

所以我们其实就只要看一看现在去应聘的人，在这个取景范围里面，他是不是有这么多人。

也具备了区间的总人数，我们可以用前缀和。

我们就可以把它变成不等式：

r_i \le s_i - s_{i - 8}

。

s

数组是前缀和。

然后关键这个阶段的一个难点在于我怎么去解决这个环形问题。

那有人可能想到，是不是要需要复制呢？

我们可以写成

s_i \ge s_{i -1}

。

所以最小出纳员数量是

s_{24}

。

那我们的正解就出来了，直接用枚举或二分就可以了。

接下来，上代码！~~码风可能有点奇怪~~

CPP

#include <bits/stdc++.h>
using namespace std;
int n,c[1005],r[1005],dis[1005],f[1005],vis[1005],cnt[1005];
struct node
{
    int id,w;
};
vector <node> v[1005];
bool SPFA(int x)//SPFA判负环
{
    queue <int> q;
    q.push(0);
    dis[0] = 0;
    f[0] = 1;
    cnt[0] = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        f[t] = 0;
        for(auto i : v[t])
        {
            if(dis[i.id] >= dis[t] + i.w) continue;
            dis[i.id] = dis[t] + i.w;
            cnt[i.id] = cnt[t] + 1;
            if(cnt[i.id] >= 24) return 0;
            if(f[i.id]) continue;
            f[i.id] = 1;
            q.push(i.id);
        }
    }
    return dis[24] == x;
}
bool check(int x)//判断雇佣x人是否可行
{
    for(int i = 0; i <= 24; i++)
    {
        v[i].clear();
        dis[i] = -1e9;
        cnt[i] = 0;
        f[i] = 0;
    }
    v[0].push_back({24,x});
    for(int i = 1; i <= 24; i++)
    {
        v[0].push_back({i,0});
        v[i - 1].push_back({i,0});
        v[i].push_back({i - 1,-c[i]});
        if(i > 8) v[i - 8].push_back({i,r[i]});
        else v[i + 16].push_back({i,r[i] - x});
    }
    return SPFA(x);
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(c,0,sizeof c);
        for(int i = 1; i <= 24; i++) cin >> r[i];
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            int xx;
            cin >> xx;
            c[xx + 1]++;
        }
        bool ff = 0;
        for(int i = 0; i <= n; i++)
        {
            if(check(i))
            {
                cout << i << "\n";
                ff = 1;
                break;
            }
        }
        if(!ff) cout << "No Solution\n";
    }
    return 0;
}

千万千万不要，复制题解代码

都看到这里了，麻烦点个赞吧！

题解：P10941 Cashier Employment

文章操作

题意：

正解：

相关推荐

评论

题解：P10941 Cashier Employment