HDU1434 幸福列车【模拟+优先队列】（老师程序代码注释）_幸福列车 hdu1434-程序员宅基地

技术标签： HDU

幸福列车

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 3050 Accepted Submission(s): 993

Problem Description

一批幸福的列车即将从杭州驶向幸福的终点站——温州，身为总列车长的linle有一些奇怪的癖好。

他会记录下全部乘客的名字（name）和他们的人品值（RP），根据这些将他们排序，并不时地从某辆列车里踢出人品最不好（RP值最低）的一个人，当两个人人品一样不好时，他就会踢出名字难听的人（linle认为按字典顺序，排在越在后面的人名字越难听）。

当然出于列车行驶需要，他还会不时的发布一些命令，比如让某个乘客上车，合并某两辆列车等。

linle的上一任秘书***因为不能高效地执行他的这些命令而被炒鱿鱼，他现在正在寻觅新的秘书人选，你能不能胜任呢？（谢绝男士，待遇丰厚~~~）

Input

本题包含多组测试，请处理到文件结束。
对于每一组测试，第一行包含两个整数 N ，M ，表示一共有N( N<=10000 ) 辆列车，执行M( M<=10000 )次操作。
接下来有 N （从1开始记数）辆列车的信息，每辆列车先有一个数字 Xi(1 <= Xi <= 100 )，表示该列车有Xi个乘客，接下来Xi行乘客信息，每个乘客包含名字（20个字符以内，不包含空白符）和人品（0<= RP <=30000）。
再接下来有 M 行操作信息，一共有3种操作，分别为

GETON Xi name RP 表示有一个叫name的人品为RP的人登上第Xi列车

JOIN Xi Xj 表示有将第Xj辆列车合并到Xi辆列车

GETOUT Xi 表示从第Xi辆列车踢出一个人品最差的人

测试数据保证每个操作均合法，即不会将已经被合并到其他列车的列车再进行合并，也不会从一辆空列车里踢出乘客

Output

对于每个 GETOUT 命令，输出被踢出的那个人的名字

Sample Input

3 5

xhd 0

zl 1

8600 1

ll 2

Ignatius 3

GETOUT 1

JOIN 1 2

GETOUT 1

GETON 3 hoho 2

GETOUT 3

Sample Output

xhd

hoho

Hint

Huge input, scanf is recommended.

Author

linle

Source

ACM暑期集训队练习赛（四）

Recommend

lcy

/* HDU1434 幸福列车 */
 
#include <iostream>
#include <queue>
 
using namespace std;
 
const int N = 10000;
 
struct _node {
    string name;
    int rp;
    friend bool operator < (_node a, _node b) {//运算符重载 
        if(a.rp != b.rp)
            return a.rp > b.rp;
        else
            return a.name < b.name;
    }//排序，将队列中的人按照题意进行排序，以便后续直接踢出 
};
 
int main()
{
    std::ios::sync_with_stdio(false);//加快c++的输入输出速度的代码 
 
    int n, m, xi, xj;
 
    while(cin >> n >> m) {
        priority_queue<_node> q[N+1];
        _node t;   // 临时的 
 
        for(int i=1; i<=n; i++) {
            cin >> xi;
            while(xi--) {
                cin >> t.name >> t.rp;//读入人名和人品 
 
                q[i].push(t);//push到第i个队列 
            }//31__38都是初始化代码 
        }
 
        while(m--) {//模拟m个指令，做m个循环 
            string op;
 
            cin >> op;//读入命令 
            if(op == "GETON") {//根据不同的命令做判断，做不同的处理，geton是上车 
                cin >> xi >> t.name >> t.rp;
 
                q[xi].push(t);
            } else if(op == "JOIN") {//把一个车厢里面的人导入另一个车厢 
                cin >> xi >> xj;
                while(!q[xj].empty()) {
                    t = q[xj].top();//先暂存在t中，在导入xi中，也可以直接导，不用存在t中了，比较繁琐 
                    q[xi].push(t);
                    q[xj].pop();//xj中的释放 
                }
            } else if(op == "GETOUT") {
                cin >> xi;
                t = q[xi].top();//找在前面的人，踢出 
                cout << t.name << endl;
                q[xi].pop();
            }
        }
    }
 
    return 0;
}


/*
输入：
 
3 5         三辆列车，执行5次操作 
2           有两个人在一车厢 
xhd 0       名字xhd 人品0 
zl 1        名字zl人品1
2           有两个人在二车厢 
8600 1      名字8600 人品1
ll 2        名字ll 人品2 
1           有一个人在三车厢  
Ignatius 3  名字 Ignatius，人品2  
GETOUT 1    一车厢踢出一个人 
JOIN 1 2    合并一、二车厢 
GETOUT 1    一车厢踢出一个人 
GETON 3 hoho 2  三车厢上了一个名字hoho，人品为2的人 
GETOUT 3    三车厢踢出一个人 

输出：
xhd
zl
hoho

 
分析：
有几个车厢，就得有几个队列，而且得是优先队列。 
合理的数据结构表示是关键 
*/

本文链接：https://blog.csdn.net/xiaorui98/article/details/81168913

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【yolov8系列】将yolov8-seg 模型部署到瑞芯微RK3566上_yolov8 rknn-程序员宅基地

文章浏览阅读3.7k次，点赞7次，收藏43次。前言之前记录过，整体比较流畅，记录了onnx转rknn的相关环境配置，使用的rk版本为rknn-toolkit2-v1.4.0。当前库已经更新为1.5，这里还是沿用1.4的版本进行记录。本篇博客是在上篇博客（yolov5的rk3566的部署）的基础上，记录下yolov8n-seg的模型在3566上的部署过程。若精度异常可查看官方提供文档，写的比较详细。这里说明下自己遇到的问题：yolov8模型模型进行全量化结果异常yolov8模型在PC端模拟器的运行结果时，板端运行结果异常。_yolov8 rknn

【java并发】传统线程技术中的定时器技术_java 定时器如何解决并发问题-程序员宅基地

文章浏览阅读4.9k次，点赞4次，收藏2次。传统线程技术中有个定时器，定时器的类是Timer，我们使用定时器的目的就是给它安排任务，让它在指定的时间完成任务。所以先来看一下Timer类中的方法（主要看常用的TimerTask()方法）：_java 定时器如何解决并发问题

windows下nginx的启动部署_set nginx_path-程序员宅基地

文章浏览阅读1.2w次，点赞5次，收藏16次。一、安装部署1、下载完成后，解压缩，运行cmd，使用命令进行操作，不要直接双击nginx.exe，一闪而过，根本起不来，一定要在dos窗口启动2、使用命令到达nginx的加压缩后的目录cd e:\nginx-1.173、启动nginx服务，启动时会一闪而过是正常的start nginx4、查看任务进程是否存在，dos或打开任务管理器都行tasklist..._set nginx_path

VIP视频解析的一丢丢骚操作-程序员宅基地

文章浏览阅读3k次。大周末的挺多人窝在家看剧的，现在普遍要各种VIP了。所以很多人也会找一些VIP解析网站来观看。我看剧少，偶尔也会用上这么些网站，平常的操作是：打开视频复制网址→打开解析网站粘贴网址，然后开始享受龟速播放哈哈。这要动那么多下手指，多少有点不够优雅，所以就临时学了一手骚操作——浏览器书签，哪里需要点哪里，打开视频后再点下书签就够了。1. 新建书签随便拿个网站保存成书签即可。2. 了解原理以下是临时学的..._解析

深入GPU硬件架构及运行机制-程序员宅基地

文章浏览阅读1.9k次，点赞7次，收藏55次。目录一、导言 1.1 为何要了解GPU？ 1.2 内容要点 1.3 带着问题阅读二、GPU概述 2.1 GPU是什么？ 2.2 GPU历史 2.2.1 NV GPU发展史 2.2.2 N..._gpu page table作用

C语言常见基础错误大全总结_c语言错误提示大全-程序员宅基地

文章浏览阅读7.9k次，点赞19次，收藏150次。1.语句分号错误，引号后忘记加逗号，大小写错误scanf("%c",&a);2.输入中的取地址符错误int a;scanf("%d", &a); //&a 表示变量 a 的地址，&是取地址符char a;scanf("%c",&a);char a[100];scanf("%s",a);3.类型及其范围是否错误。这里只给整型。前提：一个字节=8位int、long、long long取值范围short int 1个字节储存short_c语言错误提示大全

随便推点

React antd表单控件+栅格系统控制label长度_react 表单 fields 长度-程序员宅基地

文章浏览阅读2.4k次。import React from 'react'import moment from 'moment';//cnpm i moment --saveimport { Card, Form, Input, Button, Checkbox, Radio, Select, Switch, DatePicker, TimePicker, Upload, Icon, message, InputNumber } from 'antd'const { Option } = Select;const { T._react 表单 fields 长度

elementUI分页中改变current-page绑定的值无效问题的解决_分页组件js直接修改页码绑定值不触发事件-程序员宅基地

文章浏览阅读8.3k次，点赞5次，收藏16次。问题今天在使用elementUI分页组件el-pagination时，在方法中修改current-page绑定的值，正常来说页面上显示的当前所在的页码会随着改变，但是并没有。分页代码：<el-pagination background @size-change="handleSizeChange" @current-change="handleCurrentChange" :current-page="currentPage" :page-_分页组件js直接修改页码绑定值不触发事件