Contest1480 - ZZNU17级暑期集训——单人挑战赛（Final）（ZZNU 2145AK王国系列问题-百官排序）

81 阅读 0 评论 54 点赞

我是靠谱客的博主失眠含羞草，最近开发中收集的这篇文章主要介绍Contest1480 - ZZNU17级暑期集训——单人挑战赛（Final）（ZZNU 2145AK王国系列问题-百官排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2145: AK王国系列问题-百官排序

时间限制: 1 Sec 内存限制: 256 MB
提交: 55 解决: 29
[提交] [状态] [讨论版] [命题人:admin]

题目描述

AK王国的前任国王喜欢凭自己的喜好给文武百官排序。

已知有N位文武官员，他们的编号由1到N。他们一开始的顺序是N的一个全排列。

前任国王喜欢执行以下两种操作：

FIRST X: 将编号为X的文武官员移到所有文武官员前面。

LAST X: 将编号为X的文武官员移到所有文武官员后面。

前任国王在位期间执行了p次这样的操作。

由于你可能要继承他的王位，所以你要知道文武官员现在的排序。

输入

第一行输入一个正整数 N，表示有N位文武官。

第二行输入 N 个正整数，Q1, Q2, Q3, ... ..., QN，Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。

第三行输入一个正整数 P，表示接下来要进行的操作次数。

接下来 P 行，第 i 行输入一个字符串 Si 以及一个正整数 Xi，表示一次操作。

1 ≤ N ≤ 10^5.

1 ≤ Qi ≤ N.

1 ≤ P ≤ 10^5.

Si 属于 { “FIRST”, “LAST” }.

1 ≤ Xi ≤ 10^5.

输出

输出 N 个正整数，表示 P 次操作之后文武官的顺序。

样例输入
4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1
样例输出
4 3 2 1

思路：用一个数组去存它的位置，每次操作更新它的位置，元素从1e5那个位置开始存，到1e5+n-1；

这样虽然占用内存多，但是每次查询一个位置时间复杂度为o(1)，存储一个元素也是o(1),大量节省了时间。

由于最多操作10^5次，极端情况下就是往前操作10^5次/往后操作10^5次，我们可以开辟一个

3e5的数组，每次操作，就让它存前面或后面，把被操作的那个数的原先位置对应的,a[i]置为0,并更新被操作元素的位置。

代码实现(题目链接)：

#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=3e5+7;
int a[maxn],b[maxn];
char str[5];
void table(int a[],int n)
{
for(int i=1e5;i<=n+100000;i++)
{
b[a[i]]=i;
}
}
int main()
{
int n,m,p,t,i,w;
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for( i=1e5;i<1e5+n;i++)
{
scanf("%d",&a[i]);
}
table(a,n);
t=n+1e5;
w=100000;
scanf("%d",&m);
while(m--)
{
scanf("%s%d",str,&p);
if(strcmp(str,"FIRST")==0)
{
a[--w]=p;
a[b[p]]=0;
b[p]=w;
}
else if(strcmp(str,"LAST")==0)
{
a[++t]=p;
a[b[p]]=0;
b[p]=t;
}
}
for(i=0;i<=maxn;i++)
{
if(a[i]!=0)
printf("%d ",a[i]);
}
printf("n");
}
return 0;
}