題目描述

一個學校里老師要將班上 N 個同學排成一列，同學被編號為 1～N，他采取如下的方法：

目前創(chuàng)新互聯(lián)已為近千家的企業(yè)提供了網站建設、域名、虛擬主機、成都網站托管、企業(yè)網站設計、大埔網站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

1. 先將 1 號同學安排進隊列，這時隊列中只有他一個人；

2. 2～N 號同學依次入列，編號為 i 的同學入列方式為：老師指定編號為 i 的同學站在編號為 1～(i?1) 中某位同學（即之前已經入列的同學）的左邊或右邊；

3. 從隊列中去掉 M 個同學，其他同學位置順序不變。

在所有同學按照上述方法隊列排列完畢后，老師想知道從左到右所有同學的編號。

輸入格式

第一行一個整數 N，表示了有 N 個同學。

第 2～N 行，第 i 行包含兩個整數k,p，其中 k 為小于 i 的正整數，p 為 0 或者 1。若 p 為 0，則表示將 i 號同學插入到 k 號同學的左邊，p 為 1 則表示插入到右邊。

第 N+1 行為一個整數 M，表示去掉的同學數目。

接下來 M 行，每行一個正整數 x，表示將 x 號同學從隊列中移去，如果 x 號同學已經不在隊列中則忽略這一條指令。

輸出格式

一行，包含最多 N 個空格隔開的整數，表示了隊列從左到右所有同學的編號。

輸入輸出樣例

輸入 #1復制

4

1 0

2 1

1 0

2

3

3

輸出 #1復制

2 4 1

說明/提示

【樣例解釋】

將同學 2 插入至同學 1 左邊，此時隊列為：

2 1

將同學 3 插入至同學 2 右邊，此時隊列為：

2 3 1

將同學 4 插入至同學 1 左邊，此時隊列為：

2 3 4 1

將同學 3 從隊列中移出，此時隊列為：

2 4 1

同學 3 已經不在隊列中，忽略最后一條指令

最終隊列：

2 4 1

【數據范圍】

對于 20% 的數據，1≤N≤10。

對于40% 的數據，1≤N≤1000。

對于 100% 的數據，1

一開始用單鏈表寫的，里面的查詢次數直接爆了哎，這是我本來的代碼，學單鏈表插入刪除最后只能完成40%的數據（沒辦法人菜癮大）

#includeusing namespace std;
typedef struct Lnode
{
item data=0;
struct Lnode* next=NULL;
}Lnode,*linknode;
bool InitLink(linknode& s)
{
s = new Lnode;
if (s == NULL)
{
return false;
}
return true;
}
int insertitem(linknode& s, int k, int p, item e) {
linknode newLnode = new Lnode;
if (newLnode == NULL) { cout<< "內存不足，分配失敗"; return 0; }
newLnode->data = e;
linknode a = s->next;//遍歷指針1
linknode b = s;//遍歷指針2
while (a != NULL)
{
if (a->data == k)break;
b = b->next;
a = a->next;
}
//插入到左邊
if (p==0)
{
b->next = newLnode;
newLnode->next = a;
return 1;
}
//插入到右邊
newLnode->next = a->next;
a->next = newLnode;
return 1;
}
int t[100000 + 1] = {0};
int main()
{
linknode s = NULL;
if (InitLink(s) == false) { cout<< "內存不足，分配失敗"; return 0; };
linknode newfirst = new Lnode;
newfirst->data = 1;
s->next = newfirst;
int n;
cin >>n;
for (item i = 2; i<= n; i++)
{
int k, p;
cin >>k >>p;//k號同學，p值不同插入的方向不同
if (insertitem(s, k, p, i) == 0) { return 0;}
}
int m;
cin >>m;
item x;
for (int i = 0; i< m; i++)
{
cin >>x;
if (t[x] == 1) { continue; }
t[x] = 1;
linknode p = s->next;
linknode z = s;
while (p)
{
if (p->data==x)
{
linknode l = p;
z->next = p->next;
free(l);
break;
}
p = p->next;
z = z->next;
}
}
while (s)
{
if (s->data != 0) {
cout<< s->data<<" ";
}
s = s->next;
}
return 0;
}

因為查找數據很慢，所以后面看別人的做法，只能驚嘆太強了，因為輸入輸出都是整數且連續(xù)直接用結構體來代替雙鏈表。太強了！??！然后我用數組實現(xiàn)循環(huán)雙鏈表，重寫這個題

#includeusing namespace std;
typedef struct stu
{
int l=0, r=0;
}students;
int main() {
int n;
cin >>n;
students  s[100000 + 5];
//構造兩個結點的循環(huán)雙鏈表
s[0].r = 1;
s[0].l = 1;
s[1].l = 0;
s[1].r = 0;
bool flag[100000 + 5] = { false };//默認不輸出
flag[1] = true;//1默認輸出
for (int i = 2; i<= n; i++)//增加
{
int k, p;
cin >>k >>p;
if (p == 0)//插入到左邊
{
s[s[k].l].r = i;
s[i].l = s[k].l;
s[i].r = k;
s[k].l = i;
}
if (p == 1)//插入到右邊
{
s[s[k].r].l = i;
s[i].r = s[k].r;
s[i].l = k;
s[k].r = i;
}
flag[i] = true;
}
int m;
cin >>m;
for (int i = 0 ; i< m ; i++)
{
int x;
cin >>x;
if (flag[x] == false)continue;
     //刪除的操作，畢竟不是真實的空間不需要free
s[s[x].l].r = s[x].r;
s[s[x].r].l = s[x].l;
flag[x] = false;
}
int p = s[0].r;
for (p =s[0].r;p!=0;p=s[p].r)
{
cout<< p<< " ";
}
return 0;
}

最后感覺還是要發(fā)散思維，確實見識太少了

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站欄目：洛谷P1160隊列安排從單鏈表到數組實現(xiàn)循環(huán)雙鏈表-創(chuàng)新互聯(lián)
當前路徑：http://jinyejixie.com/article0/csdeoo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站維護、網頁設計公司、定制開發(fā)、軟件開發(fā)、營銷型網站建設、網站導航

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)