UVA 10588—— Queuing at the doctors

红太狼 2022-07-29 09:25 171阅读 0赞

题意：给定n个工人和m个医生，然后进行体检，每个医生每秒接待一个工人，每个人都有一个体检项目顺序和时间，问最后一个员工完成体检的时间。

思路：优先队列模拟，建立m个项目的优先队列，当某个工人满足体检时间时，给该工人体检，然后push到下一个项目中去。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1005;
    
    int T,n,m;
    struct node
    {
        int t,id;
        bool operator <(const node& B)const {
            return t > B.t || (t == B.t && id > B.id);
        }
    }p;
    
    priority_queue<node>Q[N];
    queue<int>q[N];
    
    
    int sol()
    {
        int f = 1, ans = 0;
        while (f) {
        f = 0;
        for (int i = 0; i < m; i++) {
            if (!Q[i].empty()) {
            f = 1;
            node pe = Q[i].top();
            if (ans < pe.t) continue;
            Q[i].pop();
            q[pe.id].pop();
            if (!q[pe.id].empty()) {
                pe.t = ans + 1;
                Q[q[pe.id].front()].push(pe);
            }
            }
        }
        ans++;
        }
        return ans - 1;
    }
    int main()
    {
        scanf("%d",&T);
        int k,tp;
        while (T--){
            scanf("%d%d",&n,&m);
            for (int i=0;i<n;i++){ p.id=i;
            scanf("%d%d",&p.t,&k);
            for (int j=0;j<k;j++){
                scanf("%d",&tp);
                tp--;
                q[p.id].push(tp);
            }
            Q[q[p.id].front()].push(p);
            }
            //cout<<"bug"<<endl;
            printf("%d\n",sol());
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关【UVa#10325】The Lottery

Description [UVa\10325][UVa_10325] 给定n和m个数，求1~n中不被这m个数中任意一个数整除的数的个数 Solution 容斥原

青旅半醒/ 2023年06月05日 08:54/ 0 赞/ 38 阅读

相关 UVA11752 The Super Powers

最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。这道题是很久前做的，细节记不太清了。。。

深藏阁楼爱情的钟/ 2022年09月20日 12:44/ 0 赞/ 38 阅读

相关 uva 1220——Party at Hali-Bula

题意：公司里n个人，要举办一场party，但是到场的人不能碰到他的直隶上司，问最多能到场多少人。思路：树形dp，就是求在树上的最大独立集合，加唯一性特判。dp(u

Dear 丶/ 2022年08月17日 15:25/ 0 赞/ 7 阅读

相关 uva 1623——Enter The Dragon

题意：有n个装满水的湖，可以预知将来m天下雨情况，每次下满一个湖，或者不下，不下雨的时候可以让某个湖变干，问是否存在一种方案使得每次下雨之前湖总是干的。思路：贪心

以你之姓@/ 2022年08月09日 16:42/ 0 赞/ 176 阅读

相关 uva 1614——UVA 1614 - Hell on the Markets

Description [![Download as PDF][]][Download as PDF 1]Most financial institutions had be

客官°小女子只卖身不卖艺/ 2022年08月09日 14:56/ 0 赞/ 143 阅读

相关 UVA 11300 Spreading the Wealth

![Center][] include <cstdio> include <cmath> include <algorithm>

Dear 丶/ 2022年08月07日 02:38/ 0 赞/ 201 阅读

相关 UVA 10588—— Queuing at the doctors

题意：给定n个工人和m个医生，然后进行体检，每个医生每秒接待一个工人，每个人都有一个体检项目顺序和时间，问最后一个员工完成体检的时间。思路：优先队列模拟，建立m个

红太狼/ 2022年07月29日 09:25/ 0 赞/ 172 阅读

相关 uva 10254——The Priest Mathematician

题意：汉诺塔题目的变形，有4根柱子，可以把顶部的k个盘子移到最后的柱子上，然后按照汉诺塔，问最后走的最小步数。思路：递推，经过递推可以发现f\[n\] = f\[

ゝ一纸荒年。/ 2022年07月28日 01:35/ 0 赞/ 45 阅读

相关 Queuing tasks with Redis

Overview As stated on their official homepage, Redis is an open source (BSD licensed)

╰+攻爆jí腚メ/ 2022年06月16日 01:51/ 0 赞/ 111 阅读

相关 uva 701 - The Archeologists' Dilemma

[题目链接：uva 701 - The Archeologists' Dilemma][uva 701 - The Archeologists_ Dilemma]

待我称王封你为后i/ 2022年05月12日 23:28/ 0 赞/ 154 阅读