首页 > ACM题库 > HDU-杭电 > HDU 1434 幸福列车-模拟-[解题报告] C++
2013
12-10

HDU 1434 幸福列车-模拟-[解题报告] C++

幸福列车

问题描述 :

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

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

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

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

输入:

本题包含多组测试,请处理到文件结束。
对于每一组测试,第一行包含两个整数 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辆列车踢出一个人品最差的人

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

输出:

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

样例输入:

3 5
2
xhd 0
zl 1
2
8600 1
ll 2
1
Ignatius 3
GETOUT 1
JOIN 1 2
GETOUT 1
GETON 3 hoho 2
GETOUT 3

样例输出:

xhd
zl
hoho

Hint
Huge input, scanf is recommended.

链表模拟 ,优先队列,链表合并,加上恶心的WA….

#include <iostream>
#include <string>
#include <list>
#include  <vector>
#include <set>
#include <algorithm>
#include <fstream>

struct passger
{
	friend bool operator<(const passger& l,const passger& r);
	std::string name;
	int rp;
};

bool operator<(const passger& l,const passger& r)
{
	if(l.rp<r.rp){
		return true;
	}else if(l.rp==r.rp){
		return l.name>r.name;
	}
	return false;
}

struct car
{
	std::vector<passger> pas;
	int num;
};

car unit;

std::list<car > train;
typedef std::list<car >::iterator tritr_t; 
typedef std::vector<passger>::iterator psitr_t;

tritr_t itr,itr2;
psitr_t psitr;
int n,m,xi;
std::string command;
passger tmp;
std::string nm;
int var1,var2;

bool pr_insert(std::vector<passger>& vec, passger& tmp)
{
	psitr_t psitr;
	if(tmp<vec[0]){
		itr->pas.insert(vec.begin(),tmp);
		return true;
	}else{
		for(psitr=vec.begin();psitr!=vec.end();psitr++){
			if(*psitr<tmp){
				continue;
			}else{
				vec.insert(psitr+1,tmp);
			}
		}
		if(psitr==vec.end()){
			vec.push_back(tmp);
		}
		return true;
	}
	return false;

}
   int main()
{
//	std::ifstream fi("1.txt"); 
	while (std::cin>>n>>m){
		for(int i=0;i!=n;i++){
			std::cin>>xi;
			for(int j=0;j!=xi;j++){
				std::cin>>tmp.name>>tmp.rp;
				unit.pas.push_back(tmp);
			}
			std::sort(unit.pas.begin(),unit.pas.end());
			unit.num=i;
			train.push_back(unit);
			unit.pas.clear();
		}

		for(int i=0;i!=m;i++){
			std::cin>>command;
			if(command=="GETON"){

				std::cin>>var1>>tmp.name>>tmp.rp;
				for(itr=train.begin();itr!=train.end();itr++){
					if(itr->num==var1-1){

				         pr_insert(itr->pas,tmp);
					}
				}
			}else if(command=="GETOUT"){

				std::cin>>var1;
				for(itr=train.begin();itr!=train.end();itr++){
					if(itr->num==var1-1){
						std::cout<<itr->pas[0].name<<std::endl;
						itr->pas.erase(itr->pas.begin());
						break;
					}
				}
			}else if(command=="JOIN"){

				std::cin>>var1>>var2;
				for(itr=train.begin();itr!=train.end();itr++){
					if(itr->num==var1-1){
						break;
					}
				}
				for(itr2=train.begin();itr2!=train.end();itr2++){
					if(itr2->num==var2-1){
						for(psitr=itr2->pas.begin();psitr!=itr2->pas.end();psitr++){
							pr_insert(itr->pas,*psitr);
						}
						train.erase(itr2);
						break;
					}
				}
			}
		}

		train.clear();
	}
}

解题报告转自:http://blog.csdn.net/emiyasstar__/article/details/8907317


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  3. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  4. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。