网站备案上传照片几寸,上海网站排名提升,大型定制网站最贵建设多少钱,网站开发 架构题目
一个学校里老师要将班上N个同学排成一列#xff0c;同学被编号为1∼N#xff0c;他采取如下的方法#xff1a; 先将1号同学安排进队列#xff0c;这时队列中只有他一个人#xff1b; 2∼N号同学依次入列#xff0c;编号为i的同学入列方式为#xff1a;老师指定编…题目
一个学校里老师要将班上N个同学排成一列同学被编号为1∼N他采取如下的方法 先将1号同学安排进队列这时队列中只有他一个人 2∼N号同学依次入列编号为i的同学入列方式为老师指定编号为i的同学站在编号为1∼(i−1)中某位同学即之前已经入列的同学的左边或右边 从队列中去掉M个同学其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后老师想知道从左到右所有同学的编号。
输入输出格式
输入格式
第一行一个整数N表示了有N个同学。
第2∼N行第i行包含两个整数k,p其中k为小于i的正整数p为0或者1。若p为0则表示将i号同学插入到k号同学的左边p为1则表示插入到右边。
第N1行为一个整数M表示去掉的同学数目。
接下来M行每行一个正整数x表示将x号同学从队列中移去如果x号同学已经不在队列中则忽略这一条指令。
输出格式
一行包含最多N个空格隔开的整数表示了队列从左到右所有同学的编号。
输入输出样例
输入样例
4
1 0
2 1
1 0
2
3
3
输出样例
2 4 1
补充知识
链表的使用可以完成以下的操作实现一个数据结构维护一张表最初只有一个元素1。支持以下的操作其中x,y都是int范围内的正整数且都不一样。
1ins_back(x,y)将元素y插入到x后面
2ins_front(x,y)将元素y插入到x前面
3ask_back(x)询问x后面的元素
4ask_front(x)询问x前面的元素
5del(x)从表中删除元素x不改变其他元素的先后顺序
struct node{int pre,nxt;//分别记录前驱和后继结点在数组s中的下标int key;node(int _key0,int _pre0,int _nxt0){pre_pre;nxt_nxt;key_key;}
};
node s[100005];
//一个池以后想要新建一个结点就从s数组里面拿出一个位置给新结点
//也可以使用指针new,delete实现
int tot0;//记录s数组目前使用了多少个位置那么下一个可用的位置就是s[tot1]
int find(int x){//查找x的结点编号需要遍历整个链表int now1;while(nows[now].key!x){nows[now].nxt;return now;}
}
void ins_back(int x,int y){//y插在x后面 int nowfind(x);s[tot]node(y,now,s[now].nxt);s[s[now].nxt].pretot;s[now].nxttot;
}
void ins_front(int x,int y){//y插在x前面 int nowfind(x);s[tot]node(y,s[now].pre,now);s[s[now].pre].nxttot;s[now].pretot;
}
int ask_back(int x){int nowfind(x);return s[s[now].nxt].key;
}
int ask_front(int x){int nowfind(x);return s[s[now].pre].key;
}
void del(int x){int nowfind(x);int les[now].pre,rts[now].nxt;s[le].nxtrt;s[rt].prele;
}
当然STL库也提供了链表的相关操作需要使用list的头文件。支持以下的常用方法。
1listint a定义一个int类型的链表a
2int arr[5]{1,2,3};lsitint a(arr,arr3)从数组arr中的前三个元素作为链表a的初始值
3a.size()返回链表的结点数量
4listint::iterator it定义一个名为it的迭代器指针
5a.begin();a.end()链表开始和末尾的迭代器指针
6it;it--迭代器指向前一个和后一个元素
7a.push_front(x);a.push_back()在链表开头或者末尾插入元素x
8a.insert(it,x)在迭代器it的前插入元素x
9a.pop_front();a.pop_back()删除链表开头或者末尾
10a.erase(it)删除迭代器it所在的元素
11for(ita.begin();it!a.end();it)遍历链表
解析
此题目利用一个双向链表维护这个队伍每个同学记录自己左边和右边的同学。这样各种操作都可以的复杂度完成。可以使用上面的链表模板但是需要稍微修改一下插入函数和删除函数。使用数组index定位某位同学的结点编号在插入和删除时直接找到这位同学的结点编号在插入时还要记录下这名同学的结点编号。这样就不需要每次都要遍历整个链表了。
#includeiostream
using namespace std;
struct node{int pre,nxt,key;node(int _key0,int _pre0,int _nxt0){pre_pre;nxt_nxt;key_key;}
};
node s[100005];
int n,m,tot0,index[100005]{0};//记录每个位置的结点编号
void ins_back(int x,int y){int nowindex[x];//查找索引s[tot]node(y,now,s[now].nxt);s[s[now].nxt].pretot;s[now].nxttot;index[y]tot;//记录索引
}
void ins_front(int x,int y){int nowindex[x];s[tot]node(y,s[now].pre,now);s[s[now].pre].nxttot;s[now].pretot;index[y]tot;
}
void del(int x){int nowindex[x];int les[now].pre,rts[now].nxt;s[le].nxtrt;s[rt].prele;index[x]0;
}
int main(){int x,k,p,now;cinn;s[0]node();//令0恒为最左边的结点ins_back(0,1);for(int i2;in;i){cinkp;p ? ins_back(k,i):ins_front(k,i);}cinm;for(int i1;im;i){cinx;if(index[x]){del(x);}}nows[0].nxt;while(now){couts[now].key ;nows[now].nxt;}return 0;
}
