b944: 好想上廁所(男廁篇)

2019-08-22

內容

有一天，小明急急忙忙的衝到了某間廁所，(不要問我為什麼是小明)

卻發現廁所的某種規律!(不要問我為什麼小明急著上廁所還可以發現規律)

首先，他發現男生們上廁所都會儘量相隔一個小便斗，(不要問我為什麼會這樣)

除非他們找不到能夠相鄰一個小便斗的小便斗，

才會勉為其難的使用其他的小便斗，

若是沒有小便斗，就只好轉身向著遙遠彼方的閃耀廁所奔去，

這嚴重地影響了男生廁所的效率(其實並沒有)，

小明想要寫一個程式，觀察男生廁所的使用狀況~~(其實你是變態是吧?)

輸入

一開始給予一個整數 n (0<n<21)，作為小便斗的數量上限。

然後給予兩個整數 a，b (0<=a,b<2147483647)，作為下一個男生的編號和使用時間。

測資讀入直到 EOF。所有的男生搜尋空閒小便斗時都會從編號最小的開始找。

如果使用時間為 0，依然會佔用小便斗直到下一個人進來。

3
1 5
2 4
3 3
4 2
5 1

輸出

每次輸出共有兩行或三行，

若該次輸入的使用者找不到小便斗，則輸出” Not enough”，

接下來一行是全部小便斗的使用者編號，

一行是全部小便斗的使用者剩餘時間，

若該小便斗沒有人使用，則兩者皆輸出 0。

Number: 1 0 0
Time: 5 0 0

Number: 1 0 2
Time: 4 0 4

Number: 1 3 2
Time: 3 3 3

Not enough
Number: 1 3 2
Time: 2 2 2

Not enough
Number: 1 3 2
Time: 1 1 1

解題思路

有點麻煩的流程控制，搜尋小便斗時先找兩側都沒人的空便斗，沒有再找空便斗，每次都在最後才將時間遞減 (也就是輸出完該輪答案後)。

注意人上廁所的時間可以為 0 ，這種情況下要輸出編號:n 時間:0，然後將他在下一輪開前清除。

完整程式碼

AC (11ms, 100KB)

#include <stdio.h>

typedef struct Node
{
    int User, Time;
} Toilet;

int n, a, b;
Toilet list[22];

inline char serchToilet()
{
    for (int i = 1; i <= n; i++)
    {
        if (list[i].User) continue;
        for (int j = i; j <= n; j++)
        {
            if (!list[j - 1].User && !list[j].User && !list[j + 1].User)
            {
                list[j].User = a;
                list[j].Time = b;
                return 1;
            }
        }
        list[i].User = a;
        list[i].Time = b;
        return 1;
    }
    return 0;
}

int main()
{
    scanf(" %d", &n);
    while (scanf(" %d %d", &a, &b) == 2)
    {
        if (!serchToilet())
            puts("  Not enough");
        printf("Number:");
        for (int i = 1; i <= n; i++)
            printf(" %d", list[i].User);
        printf("\n  Time:");
        for (int i = 1; i <= n; i++)
        {
            printf(" %d", list[i].Time);

            if (list[i].Time < 2)
                list[i].User = list[i].Time = 0;
            else
                list[i].Time--;
        }
        putchar('\n');
    }
    return 0;
}