ZeroJudge B938: kevin 愛殺殺

kevin 身為工具人 + 一日隊輔

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

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

一開始 N 個人站成一列

編號為 1 ~ N

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

但是… 人實在太多了 0u0

隊伍蔓延了 1 公里多

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

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

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

請輸出 「0u0 …… ?」

範例測資

範例輸入範例輸出
輸入的第一行 有2個整數 N 和 M (1 <= N、M <= 106)
代表有 N 個人 站成一排 編號為 1～N
接下來一行有 M 個數字 k1、k2、…、km (1 <= k <= N)
代表 kevin 要殺掉 第 k 個人的下一個人		每次輸出被殺掉的人的編號
如果不合法 輸出”0u0 …… ?”
5 4
1 1 5 4		2
3
0u0 …… ?
5

解題思路

宣告一個 Vector<int> 來存每一個人的「下一個人是誰」，並且在宣告一個 Vector<int> 預設為 0 代表每一個人是否被殺過了。當一個人被殺掉時，要更新他的下一個人為被殺的人的下一個人。

範例程式碼－ZeroJudge B938: kevin 愛殺殺

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int>live;
    live.push_back(-1);
    vector<pair<int, int>>v;
    pair<int, int> a;
    a.first = -1;
    a.second = -1;
    v.push_back(a);
    for (int i = 1; i<=N; i++) {
        pair<int, int>tmp;
        tmp.first = i-1;
        tmp.second = i+1;
        if (i == 1) tmp.first = -1;
        if (i == N) tmp.second = -1;
        v.push_back(tmp);
        live.push_back(0);
    }
    for (int i = 0; i<M; i++) {
        int tmp;
        cin >> tmp;
        if (live[tmp] == -1) {
            cout << "0u0 ...... ?\n";
            continue;
        }
        const int next = v[tmp].second;
        if (next == -1) {
            cout << "0u0 ...... ?\n";
            continue;
        }
        cout << next << "\n";
        live[next] = -1;
        v[tmp].second = v[next].second;
    }
}

//ZeroJudge B938
//Dr. SeanXD
標籤

相關文章

發佈留言