一道C++编程题

Question

插队
描述
北航食堂的拥挤是出了名的，不过幸好大家的整体素质比较高，所以食堂大体井然有序，但是也不排除有异类的存在。今天，我们就要好好监控一下他们
现在有n个人要在同一个窗口排队打饭，他们到达的前后顺序已知，但是有m个人已经找好了插队的同伙，例如A和B商量好，如果A在B之前到，B就可以插在A的前面，对于A而言同样如此。现在希望大家根据已知的到达顺序，和商量好准备插队的同伙信息，给出最终的打饭顺序。
请注意，这里不考虑已经打完饭无法插队的情况，并且插队的同伙关系不具有传递性，即A和B商量好，B和C商量好不代表A和C已经商量好。
输入
第一行为一个正整数t，表示公有t组数据
每组数据中
第1行为两个整数n、m，中间用空格隔开（1<=m,n <=100）
第2行共有n个正整数，表示n个人到达的先后顺序。
第3行至第m+2行每行各有2个正整数a，b，表示a和b已经商量好了
输出
每组数据输出一行，为最终的打饭顺序。人物编号之间用空格分隔。
样例输入
1
3 1
1 2 3
1 3
样例输出
3 1 2
该题出自http://www.bianchengla.com/course/cpp09/practise/problem?id=1782

Answer 1

题目出自哪里？哪个网站？
就是对于商量好的2个人，进行先后顺序比较，先后顺序可以用数组的索引进行标记。
比较后进行交换顺序。
有一个注意的就是
顺序是：1 2 3
1 3 商量了
1 2 也商量了
这个交换的顺序是怎样的？是先1 3 交换，还是1 2 交换

//超时，方法是双向链表，你看能不能优化一下。
#include <iostream>
#include <map>
using namespace std;

struct Node
{
int pre;
int next;
int cur;
};

int main()
{
int t,i,a,b,n,m,count,temp;
int pre,cur;
Node node,head;
map<int,Node> queue;
cin>>t;
while(t--)
{
count = 0;
pre = -1;
cin>>n>>m;
for(i=0;i<n;++i)
{
cin>>cur;
node.pre = pre;
node.cur = cur;
node.next = -1;
queue[cur] = node;
if(pre != -1)
{
queue[pre].next = cur;
}
else
{
head = node;
}
pre = cur;
}
while(m--)
{
cin>>a>>b;
node = queue[a];
while(node.pre!=-1)
{
if(node.pre == b)//b在a的前面
{
//将a从当前位置删除
queue[queue[a].pre].next=queue[a].next;
queue[queue[a].next].pre=queue[a].pre;
//在b前面插入a
queue[a].next = b;
queue[a].pre = queue[b].pre;
if(queue[b].pre == -1)
{
head = queue[a];
}
queue[b].pre = a;
break;
}
node = queue[node.pre];
}
//a在b的前面
if(node.pre == -1)
{

//将b从当前位置删除
queue[queue[b].pre].next=queue[b].next;

queue[queue[b].next].pre=queue[b].pre;
//在a前面插入b
queue[b].next = a;
queue[b].pre = queue[a].pre;
if(queue[a].pre == -1)
{
head = queue[b];
}
queue[a].pre = b;
}
}
node = head;
while(node.next != -1)
{
cout<<node.cur<<" ";
node = queue[node.next];
}
cout<<node.cur<<endl;
}
}