（优先队列）HDU1873 看病要排队

拼搏现实的明天。 2022-03-17 01:38 189阅读 0赞

**题目链接：**[（优先队列）HDU1873 看病要排队][HDU1873]

**题解**：数值不大，直接模拟实现的。当然也可以用优先队列，见第二个代码。

代码1：直接模拟。

//直接模拟 
    #include<iostream>
    #include<queue>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    const int maxn = 2010;
    const int INF=0x3f3f3f3f;
    
    typedef struct Node{
        int x,y;
    }Node;
    Node mes[maxn];
    int vis[maxn];
    
    int main()
    {
        char s[5];
        int n,m;
        while(~scanf("%d",&n)){
            memset(vis,0,sizeof(vis));
            int r=1;
            while(n--){
                scanf("%s",s);
                if(strcmp(s,"OUT")==0){
                    scanf("%d",&m);
                    int mx=0,ans;
                    for(int i=1;i<r;i++){
                        if(!vis[i]&&mes[i].x==m&&mx<mes[i].y){
                            mx=mes[i].y;
                            ans=i;
                        }
                    }
                    if(mx==0){
                        printf("EMPTY\n");
                    }else{
                        vis[ans]=1;
                        printf("%d\n",ans);
                    }
                }else{
                    scanf("%d%d",&mes[r].x,&mes[r].y);
                    r++;
                }
            }
        }
        return 0;
    }

代码 2：优先队列实现。

注意优先队列比较函数的写法，正好跟一般结构体的相反。

#include<iostream>
    #include<queue>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    const int maxn = 2010;
    const int INF=0x3f3f3f3f;
    
    typedef struct Node{
    	int y,id;
    	bool operator < (const Node &A)const{
    		if(y!=A.y) return y<A.y;
    		return id>A.id;
    	}
    }Node;
    Node tmp;
    
    int main()
    {
        char s[5];
        int n,m,x;
        while(~scanf("%d",&n)){
        	priority_queue<Node> pq[4];
        	int r=1;
        	while(n--){
    	    	scanf("%s",s);
    	    	if(strcmp(s,"OUT")==0){
    	    		scanf("%d",&m);
    				if(pq[m].empty()){
    					printf("EMPTY\n");
    				}else{
    					printf("%d\n",pq[m].top().id);
    					pq[m].pop();
    				}
    			}else{
    				scanf("%d%d",&x,&tmp.y);
    				tmp.id=r;
    				pq[x].push(tmp);
    				r++;
    			}
    		}
    	}
        return 0;
    }

[HDU1873]: http://acm.hdu.edu.cn/showproblem.php?pid=1873