出纳员问题

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2643 字
枚举总人数差分约束判可行性
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1510
// 题意：24 小时各时段最少需求 R(i)，N 个应聘者各有起始时刻 t（连续工作 8 小时），求最少雇佣人数，无解输出 No Solution。
// 思路：差分约束。设 T(i) 为起始时刻在 [0, i - 1] 的人数前缀和，枚举总人数 ans 后用 SPFA 判最长路是否出现正环（无解）。
// 1. 每小时人数约束：i >= 7 时 T(i + 1) - T(i - 7) >= R(i)；i < 7 时跨天，写成 T(i + 1) - T(i + 17) >= R(i) - ans。
// 2. 每个时刻上岗人数不超过该时刻的应聘者数，且 T(24) - T(0) 强制等于 ans。
// 复杂度：O(N * 25 * E) 时间 / O(25) 空间
// 易错点：i < 7 的跨天约束里含总人数 ans，减的是枚举值，漏掉这一项会算出偏小的答案。
// 易错点：ans 要从 0 枚举到 N 取第一个可行值，且 T(24) - T(0) = ans 需要正反两条边来固定。
#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[25];
int dis[25];
int cnt[25];
bool inq[25];
int R[24];
int num[24];
bool feasible(int ans){
    for(int i = 0; i <= 24; i++){
        g[i].clear();
    }
    Edge e1;
    e1.to = 24;
    e1.w = ans;
    g[0].push_back(e1);
    Edge e2;
    e2.to = 0;
    e2.w = -ans;
    g[24].push_back(e2);
    for(int i = 0; i < 24; i++){
        Edge up;
        up.to = i + 1;
        up.w = 0;
        g[i].push_back(up);
        Edge down;
        down.to = i;
        down.w = -num[i];
        g[i + 1].push_back(down);
    }
    for(int i = 7; i < 24; i++){
        Edge e;
        e.to = i + 1;
        e.w = R[i];
        g[i - 7].push_back(e);
    }
    for(int i = 0; i < 7; i++){
        Edge e;
        e.to = i + 1;
        e.w = R[i] - ans;
        g[i + 17].push_back(e);
    }
    queue<int> q;
    for(int i = 0; i <= 24; i++){
        dis[i] = 0;
        cnt[i] = 0;
        inq[i] = true;
        q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int w = g[u][i].w;
            if(dis[v] < dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v]++;
                if(cnt[v] > 25) return false;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return true;
}
int main(){
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        for(int i = 0; i < 24; i++){
            cin >> R[i];
        }
        int N;
        cin >> N;
        for(int i = 0; i < 24; i++){
            num[i] = 0;
        }
        for(int i = 0; i < N; i++){
            int t;
            cin >> t;
            num[t]++;
        }
        int ans = -1;
        for(int i = 0; i <= N; i++){
            if(feasible(i)){
                ans = i;
                break;
            }
        }
        if(ans < 0) cout << "No Solution" << "\n";
        else cout << ans << "\n";
    }
    return 0;
}
出纳员问题

正文

一本通·提高篇的其它内容
