2011-06-28 22:35:18Morris
d718. Waiting In Line
d718. Waiting In Line
/**********************************************************************************/
/* Problem: d718 "Waiting In Line" from */
/* Language: C */
/* Result: AC (50ms, 1696KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-28 18:26:29 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define label 1000001
#define N 1001
short team[label] = {};
char Used[label] = {};
struct list {
int tag;
struct list *next;
}*head, *curr, *prev, *set[N];
main() {
int a, n, m, x;
char s[8], C = 1;
while(scanf("%d", &n) == 1) {
while(n--) {
scanf("%d", &m);
while(m--)
scanf("%d", &x), team[x] = n, Used[x] = C;
set[n] = NULL;
}
head = curr = prev = NULL;
printf("Line #%d\n", C);
while(scanf("%s", s) == 1 && s[0] != 'S') {
if(s[0] == 'E') { /*insert*/
scanf("%d", &x);
curr = (struct list*)malloc(sizeof(struct list));
curr->tag = x, curr->next = NULL;
if(Used[x] != C || set[team[x]] == NULL) { /*all rear*/
if(head == NULL)
head = curr;
else
prev->next = curr;
prev = curr;
if(Used[x] == C)
set[team[x]] = curr;
}
else { /*team rear*/
if(prev == set[team[x]]) { /*all rear*/
prev->next = curr;
prev = curr;
}
else if(set[team[x]]->next != NULL) {
curr->next = set[team[x]]->next;
set[team[x]]->next = curr;
}
set[team[x]] = curr;
}
}
else {
printf("%d\n", head->tag);
curr = head;
head = head->next;
if(Used[curr->tag] == C && set[team[curr->tag]] == curr)
set[team[curr->tag]] = NULL;
free(curr);
}
}
C++;
}
return 0;
}
內容 ：
最愛馬桶洋行可愛猴子的穎妞*
常常為了買猴子玩偶去排隊
天真的她認為排隊(Waiting In Line)是生活中佇列(Queue)的好例子
也就是符合先搶先贏(First In First Out)的結構
但是她錯了...
她發現有些人在排隊時，會因為隊伍中有認識的人而進行插隊的行為!
而認識的人都是一個團體，也就是如果甲乙丙是一個團，那他們就彼此認識
而插隊的時候是排在該團的最後面，
例如若甲乙丙是一團，丁戊是一團
現在的佇列依序為 乙 戊
當甲要進佇列，就變成乙 甲 戊
當丙進來時，就變成乙 甲 丙 戊，當丁進來則變成乙 甲 丙 戊 丁
如果沒有認識的人就只好乖乖排在隊伍的最後...
心疼可愛穎妞*的你決定寫個程式
模擬這樣的插隊佇列
輸入說明
：
每組測試資料中會先輸入 N 代表有 N 個團隊 ,1 <= N <= 1000。
之後會有 N 行描述每個團體。每一行第一個數字 a 代表該團體的人數
之後接著 a 個團員的代號，為了方便，我們使用介於 0 - 999999 的正整數作為代號。
每個團隊至多只會有 1000 個團員。
另外不用考慮會有無恥的人同時屬於兩個團體以上。
接下來則是一連串的敘述，敘述有以下三種：
ENQUEUE x - 將元素 x 加入插隊佇列
DEQUEUE - 移除並回傳佇列中第一個元素
STOP - 該組測試資料的指令完畢
※注意總指令數可能高達200000個
輸出說明
：
對於每組測資，先輸出一行"Line #k" (不含引號)，k代表第幾組測資。
接著逐一印出每次 DEQUEUE 的元素，一個元素一行。
接著逐一印出每次 DEQUEUE 的元素，一個元素一行。
範例輸入 ：
2 3 1 2 3 4 4 5 6 7 ENQUEUE 1 ENQUEUE 4 ENQUEUE 3 ENQUEUE 2 ENQUEUE 8 ENQUEUE 6 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 2 3 10000 20000 30000 4 400000 500000 600000 700000 ENQUEUE 10000 ENQUEUE 400000 ENQUEUE 30000 DEQUEUE DEQUEUE ENQUEUE 700000 ENQUEUE 600000 ENQUEUE 500000 DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP
範例輸出 ：
Line #1 1 3 2 4 6 8 Line #2 10000 30000 400000 700000 600000 500000
提示
：
謝謝
liouzhou_101提醒題目敘述不清，已改正
※
2010/5/7 22:15修正測資中未換行部分
造成用pascal的同學第二筆的RE深感抱歉
感謝liouzhou_101提醒
2010/6/15 21:05 修正範例測資的錯誤
出處
：
(管理：david942j)
作法 : 鏈結 linked list 模擬
我對鏈結真的不是很熟，所以代碼很醜陋，請多多見諒
有漂亮的解法，mail 給我吧 ! 我將替您在此分享
team[] 紀錄數字 x 在哪一團
Used[] 假使數字 x 沒有在團中，那麼就是個別一個，用這個陣列做標記
*set[] 紀錄該團，最後一個的"位址"
作法 : 鏈結 linked list 模擬
我對鏈結真的不是很熟，所以代碼很醜陋，請多多見諒
有漂亮的解法，mail 給我吧 ! 我將替您在此分享
team[] 紀錄數字 x 在哪一團
Used[] 假使數字 x 沒有在團中，那麼就是個別一個，用這個陣列做標記
*set[] 紀錄該團，最後一個的"位址"
/**********************************************************************************/
/* Problem: d718 "Waiting In Line" from */
/* Language: C */
/* Result: AC (50ms, 1696KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-28 18:26:29 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define label 1000001
#define N 1001
short team[label] = {};
char Used[label] = {};
struct list {
int tag;
struct list *next;
}*head, *curr, *prev, *set[N];
main() {
int a, n, m, x;
char s[8], C = 1;
while(scanf("%d", &n) == 1) {
while(n--) {
scanf("%d", &m);
while(m--)
scanf("%d", &x), team[x] = n, Used[x] = C;
set[n] = NULL;
}
head = curr = prev = NULL;
printf("Line #%d\n", C);
while(scanf("%s", s) == 1 && s[0] != 'S') {
if(s[0] == 'E') { /*insert*/
scanf("%d", &x);
curr = (struct list*)malloc(sizeof(struct list));
curr->tag = x, curr->next = NULL;
if(Used[x] != C || set[team[x]] == NULL) { /*all rear*/
if(head == NULL)
head = curr;
else
prev->next = curr;
prev = curr;
if(Used[x] == C)
set[team[x]] = curr;
}
else { /*team rear*/
if(prev == set[team[x]]) { /*all rear*/
prev->next = curr;
prev = curr;
}
else if(set[team[x]]->next != NULL) {
curr->next = set[team[x]]->next;
set[team[x]]->next = curr;
}
set[team[x]] = curr;
}
}
else {
printf("%d\n", head->tag);
curr = head;
head = head->next;
if(Used[curr->tag] == C && set[team[curr->tag]] == curr)
set[team[curr->tag]] = NULL;
free(curr);
}
}
C++;
}
return 0;
}