Description
現定義關鍵點為一條鏈中處于中間位置的節點，例如 1 3 4中，3就是這個整數鏈中的關鍵點。

現在小玉得到了一個整數鏈，確保鏈中的各個數都互不相同且數列中數的個數為奇數。

可是，由于小玉的一些特殊要求，她可能會對這個鏈進行一些特別的操作。

操作 1 ：給定兩個數a和b，每次刪除鏈中值為a和值為b兩個節點。
操作 2 ：給定兩個數a和b，每次在鏈中值為1的節點后插入a，在鏈中值為2的節點后插入b。
由于小玉特殊的要求，她保證鏈中肯定會有值為1和2的節點，并且這兩個節點永遠不會被刪除。保證在插入操作之后鏈中始終不會有重復值的節點。

現在請你寫出一個程序，幫助小玉找出鏈中的關鍵點。

Input
只有一組數據

先輸入一個整數n（10<=n<=100000）,且保證n一定為奇數

接下來輸入n個互不相同的整數num（1<=num<=10000000)

接著下一行輸入一個整數m（1<=m<=4000)

代表接下來有m行

每行有3個數aa,bb,cc. 其中第一個數aa表示操作類型，aa為1代表刪除鏈中值為bb和cc的數，

aa為2代表在鏈中值為1的節點后增加值為bb的節點，在鏈中值為2的節點后增加值為cc的節點。

（保證刪除的節點在鏈中一定有，保證插入的節點與鏈中已有節點不會重復）

Output
對于每次操作，輸出一個值h，代表操作完成后鏈中的關鍵點。

Sample
Input
5
1 3 4 5 2
2
1 3 4
2 3 4
Output
5
5

#include<bits/stdc++.h>using namespace std;int n;typedef struct node {int data;struct node *next; } List;List *creat(int n) {List *head, *tail, *p;head = new List;head->next = NULL;tail = head;for(int i = 0; i < n; i++){p = new List;scanf("%d", &p->data);p->next = NULL;tail->next = p;tail = p;}return head; }void List_one(List *head, int a, int b) {List *p, *q;p = head;q = head->next;while(q->next)//刪除某一元素，都是找到他的前一個元素{if(q->data == a){p->next = q->next;free(q);q = p->next;n--;}else if(q->data == b){p->next = q->next;free(q);q = p->next;n--;}else//沒有相匹配的，往下移動{p = q;q = q->next;}}if(q->next == NULL)//進行特判，判斷是否要刪除的結點位于表尾{if(q->data == a){p->next = q->next;free(q);n--;}else if(q->data == b){p->next = q->next;free(q);n--;}} }void List_two(List *head, int a, int b) {List *p, *q;p = head->next;while(p)//注意與刪除操作不的不同點{if(p->data == 1){q = new List;q->data = a;q->next = p->next;p->next = q;n++;}if(p->data == 2){q = new List;q->data = b;q->next = p->next;p->next = q;n++;}p = p->next;} }int findkey(List *head, int n)//基操，不多解釋 {List *p;int m, k;m = n / 2 + 1;p = head->next;k = 1;while(k != m){p = p->next;k++;}return p->data; }int main() {int a, b, m, num, key;List *head;scanf("%d", &n);head = creat(n);scanf("%d", &m);while(m--){scanf("%d%d%d", &num, &a, &b);if(num == 1){List_one(head, a, b);}else{List_two(head, a, b);}key = findkey(head, n);printf("%d\n", key);}return 0; }

總結

以上是生活随笔為你收集整理的sdut-oj-4205-寻找关键点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。