首爾性愛美術館18禁的藝術老王現身說法關鍵字魅力!輕忽小中風,當心變殘障晚會結束續攤大腸花 學...
2013-02-27 22:52:01 人氣(248) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][?] 12207 - That is Your Queue

0
收藏
0
推薦

 

Your government has finally solved the problem of universal health care!  Now everyone, rich or poor, will finally have access to the same level of medical care.  Hurrah!

 

There's one minor complication.  All of the country's hospitals have been condensed down into one location, which can only take care of one person at a time.  But don't worry!  There is also a plan in place for a fair, efficient computerized system to determine who will be admitted.  You are in charge of programming this system.

 

Every citizen in the nation will be assigned a unique number, from 1 to P (where P is the current population).  They will be put into a queue, with 1 in front of 2, 2 in front of 3, and so on.  The hospital will process patients one by one, in order, from this queue.  Once a citizen has been admitted, they will immediately move from the front of the queue to the back.

 

Of course, sometimes emergencies arise; if you've just been run over by a steamroller, you can't wait for half the country to get a routine checkup before you can be treated!  So, for these (hopefully rare) occasions, an expedite command can be given to move one person to the front of the queue. Everyone else's relative order will remain unchanged.

 

Given the sequence of processing and expediting commands, output the order in which citizens will be admitted to the hospital.

 

Input

Input consists of at most ten test cases.  Each test case starts with a line containing P, the population of your country (1 ≤ P ≤ 1000000000), and C, the number of commands to process (1 ≤ C ≤ 1000).

 

The next C lines each contain a command of the form "N", indicating the next citizen is to be admitted, or "E x", indicating that citizen x is to be expedited to the front of the queue.

 

The last test case is followed by a line containing two zeros.

 

Output

For each test case print the serial of output. This is followed by one line of output for each "N" command, indicating which citizen should be processed next.  Look at the output for sample input for details.

 

Sample Input                              Output for Sample Input

3 6

N

N

E 1

N

N

N

10 2

N

N

0 0

 

Case 1:

1

2

1

3

2

Case 2:

1

2

 



自己做一個 linked list, 儲存區段。

原本還想用 maintain 的函數,也就是合併線段。

//0.012 s 測試數據如最下方
#include <stdio.h>
struct seg {
    int l, r;
    seg *next;
};
seg *head, *tail;
void init(int p) {
    head = new seg;
    tail = head;
    head->l = 1, head->r = p;
    head->next = NULL;
}
void delQ() {
    seg *prev;
    while(head) {
        prev = head;
        head = head->next;
        delete prev;
    }
}
void Noperator() {
    printf("%d\n", head->l);
    if(head->l == head->r) {
        tail->next = head;
        tail = head;
        head = head->next;
        tail->next = NULL;
    } else {
        seg *p = new seg;
        p->l = p->r = head->l;
        head->l++;
        tail->next = p;
        tail = p;
        tail->next = NULL;
    }
}
void Eoperator(int x) {
    if(x == head->l)
        return;
    seg *p, *q;
    p = head, q = NULL;
    while(x < p->l || x > p->r)
        q = p, p = p->next;
    if(p->l == x && x == p->r) { // move 1 block
        q->next = p->next;
        p->next = head;
        head = p;
        if(tail == p)
            tail = q;
        return;
    }
    if(p->l == x) { // split 2 block
        p->l++;
    } else if(p->r == x) { // split 2 block
        p->r--;
    } else { // split 3 block
        q = new seg;
        q->l = x+1;
        q->r = p->r;
        q->next = p->next;
        p->next = q;
        p->r = x-1;
        if(p == tail)
            tail = q;
    }
    q = new seg;
    q->l = q->r = x;
    q->next = head;
    head = q;
}
void printQ() {
    seg *p = head;
    while(p) {
        printf("(%d %d)", p->l, p->r);
        p = p->next;
    }
    printf("*%d %d*", tail->l, tail->r);
    puts("");
}
int main() {
    int P, C, x, cases = 0;
    char cmd[10];
    while(scanf("%d %d", &P, &C) == 2 && P) {
        init(P);
        printf("Case %d:\n", ++cases);
        while(C--) {
            scanf("%s", cmd);
            if(cmd[0] == 'N')
                Noperator();
            else {
                scanf("%d", &x);
                Eoperator(x);
            }
            //printQ();
        }
        delQ();
    }
    return 0;
}
/*
3 6
N
N
E 1
N
N
N
10 2
N
N
5 6
E 2
N
N
N
N
N
45 15
N
N
N
N
E 13
N
N
E 39
N
N
N
N
N
E 4
N
9 12
N
N
N
E 2
N
E 2
N
E 3
N
E 8
N
N
0 0
*/

12207That is Your Queue
台長:Morris
人氣(248) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][遞迴] 12208 - How Many Ones Needed?
此分類上一篇:[UVA][運算式] 12392 - Guess the Numbers

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請���入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文