Wannafly19 :A 佇列Q

NO IMAGE

應該是這個學期最後打的一場比賽了,沒想到這次題出的這麼難,就過了這一道題。真是一年下來水平一直趨於穩定啊。

這是A題的連結https://www.nowcoder.com/acm/contest/131/A。

時間限制:C/C 1秒,其他語言2秒
空間限制:C/C 262144K,其他語言524288K
64bit IO Format: %lld

題目描述

ZZT 創造了一個佇列 Q。這個佇列包含了 N 個元素,佇列中的第 i 個元素用 Qi 表示。Q1 表示隊頭元素,QN 表示隊尾元素。佇列中的元素是 N 的一個全排列。

ZZT 需要在這個佇列上執行 P 次操作,操作分兩種:
FIRST X: 將元素 X 移到隊頭。
LAST X: 將元素 X 移到隊尾。

在 P 次操作之後,ZZT 想知道佇列中的元素的排列方式,由於他最近很忙,因此需要請你幫他解決這個問題。

輸入描述:

第一行輸入一個正整數 N,表示佇列的大小。
第二行輸入 N 個正整數,Q1, Q2, Q3, ... ..., QN,Qi 表示佇列中的第 i 個元素。保證這 N 個數是 N 的一個全排列。
第三行輸入一個正整數 P,表示接下來要進行的操作次數。
接下來 P 行,第 i 行輸入一個字串 Si 以及一個正整數 Xi,表示一次操作。
1 ≤ N ≤ 105.
1 ≤ Qi ≤ N.
1 ≤ P ≤ 105.
S { “FIRST”, “LAST” }.
1 ≤ Xi ≤ 105.

輸出描述:

輸出 N 個正整數,表示 P 次操作之後的佇列。

輸入

4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1

輸出

4 3 2 1

    因為N的範圍是1e5,Q的範圍也是10e5,如果暴力求解的話最壞的情況就是每次操作1e5乘以1e5次,就是1e10,這顯然是超時的。參考劉汝佳《演算法競賽入門》第144頁6-5的例題,這道題可以用連結串列的思路來做。用兩個陣列,一個儲存這個結點的上一個節點,一個儲存下一個節點。每次操作進行一次更換就行了。

    然後要注意一點,就是這道題輸入較大,C 使用cin輸入容易超時,JAVA的Scanner輸入也會超時。

#include <stdio.h>
int main(){
int n;
scanf("%d",&n);
int next[100005];//儲存下一個節點的陣列
int last[100005];//儲存上一個節點的陣列
int arr[100005];//儲存每個數的位置
for(int i=1;i<=n;i  )scanf("%d",&arr[i]);
//儲存每個數的下節點和上節點
for(int i=1;i<n;i  ){next[arr[i]]=arr[i 1];last[arr[i 1]]=arr[i];}
//佇列中沒有0,所以把0當成頭結點的上一個和尾節點的下一個
next[arr[n]]=0;
last[arr[1]]=0;
next[0]=arr[1];
last[0]=arr[n];
int p;
scanf("%d",&p);
while(p--){
char s[10];
scanf("%s",s);
int a;
scanf("%d",&a);
if(s[0]=='F'){
//如果操作時把這個數放到頭部 
if(last[a]!=0){//判斷,如果這個數本身不在頭部 
//先連結這個數的上一個節點和下一個節點 
last[next[a]]=last[a];
next[last[a]]=next[a];
//然後把這個數插入到0和原來的頭結點中間。使得這個數變成0的下一個節點,原來的頭節點的上節點變成這個數。。。。。 
next[a]=next[0];
last[next[a]]=a;
next[0]=a;
last[a]=0;
}
}
//如果是插入到尾部,和上一個類似 
else{
if(next[a]!=0){
last[next[a]]=last[a];
next[last[a]]=next[a];
last[a]=last[0];
next[last[a]]=a;
last[0]=a;
next[a]=0;
}
}
}
//最後列印,先列印頭節點,避免出現多餘空格 
int i=next[0];
printf("%d",next[0]);
//然後順序列印下一個節點,下下一個節點。。。。直到節點為0終止操作 
while(i!=0){ 
i=next[i];
if(i!=0)printf(" %d",i);
}
printf("\n");
}