b938: kevin 愛殺殺

2019-08-21

內容

kevin 身為工具人 + 一日隊輔

一定要帶給隊員們最大的娛樂

所以他帶了一個活動叫盲人摸象

一開始 n 個人站成一列

編號為 1 ~ n

每次 kevin 都會叫編號 k 的人把他後面的人殺掉

但是… 人實在太多了 0u0

隊伍蔓延了 1 公里多

而 kevin 視力很差看不了那麼遠

所以請你告訴 kevin 被殺掉的是誰

如果這個這個人已經死了 or 他是最後一個人

請輸出 “0u0 …… ?”

輸入

輸入的第一行有 2 個整數 n, m (1 <= n, m <= 10 ^ 6)

代表有 n 個人站成一排編號為 1~n

接下來一行有 m 個數字 k1 k2 … km (1 <= k <= n)

代表 kevin 要殺掉第 k 個人的下一個人

5 4
1 1 5 4

輸出

每次輸出被殺掉的人的編號

如果不合法輸出”0u0 …… ?”

2
3
0u0 …… ?
5

解題思路

給每個元素一個整數指向他下一次要殺的編號，如果把他殺了，就將目標改成該死者的目標。

完整程式碼

AC (0.3s, 7.7MB)

#include <stdio.h>
#define MAX 1000010

typedef struct Node
{
    int Next;
    char Alive;
}Player;

Player list[MAX];
int n, m;

int main()
{
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 1; i <= n; i++)
        {
            list[i].Alive = 1;
            list[i].Next = i + 1;
        }
        list[n + 1].Alive = 0;
        for (int i = 0, k; i < m; i++)
        {
            scanf(" %d", &k);
            if (list[k].Alive && list[list[k].Next].Alive)
            {
                printf("%d\n", list[k].Next);
                list[list[k].Next].Alive = 0;
                list[k].Next = list[list[k].Next].Next;
            }
            else
            {
                puts("0u0 ...... ?");
            }
        }
    }
    return 0;
}