ITSA 202404 #2：點點名

某社團想玩一個遊戲，有 N 個同學排成一排，一開始從 1 開始數到 K，將第 K 個同學就表示PASS，先離開隊伍，然後接著下一位同學重新開始數 (最後一位的下一個是第一個），最後剩下的那個同學就是表演才藝，請問在已知數值得狀況下，一開始站在哪一個位置的人曾是表演才藝的人呢？

範例測資

範例輸入範例輸出
輸入一開始是一個整數 T (1 < T < 10），代表共有 T 筆測試資料。
每組測試資料共有 2 行，第一行輸入為一個正整數 N，表示參加遊戲的同學人數有 N 個 (0 < N < 100），第二行輸入為一個正整數 K 表示數到 K 的同學 PASS (K < N）。		每筆測資輸出為一個正整數 P 表示第 P 位同學必須做才藝表演，最後必須有換行字元。
2
15
4
85
2		13
43

解題思路

宣告一個 Vector<Pair<int, int>>，從第 0 個位置到第 N-1 個位置分別為所有人，Pair 分別存取每一個人的上一位和下一位是誰 (Index)。當將某一個人踢出時，更新這個人的上一位和下一位，上一位的下一位變成被踢掉的人的下一位，下一位的上一位變成被踢掉的人的上一位。宣告一個 Map<int, int>，當踢掉人的時候就將這個人的 Index 值 的 Map +1。當踢掉 N-1 個人之後，跑 for (auto it:Map)，當 it.second == 0 時，代表 it.first 沒有被踢掉，輸出 it.first。需要注意的是 Map 需要先將 0 到 N-1 都初始化為 0。

範例程式碼－ITSA 202404 #2：點點名

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++)
    {
        int N, K;
        cin >> N >> K;
        vector<pair<int, int>>num;
        map<int, int>MAP;
        for (int j = 0; j<N; j++)
        {
            pair<int, int>tmp;
            tmp.first = j-1;
            tmp.second = j+1;
            if (j == 0) tmp.first = N-1;
            if (j == N-1) tmp.second = 0;
            num.push_back(tmp);
            MAP[j] = 0;
        }
        int count = 0, kill = 0;
        while (kill != N-1)
        {
            for (int j = 0; j<K-1; j++)
            {
                count = num[count].second;
            }
            int next = num[count].second;
            num[num[count].first].second = next;
            num[num[count].second].first = num[count].first;
            kill++;
            MAP[count]++;
            count = next;
        }
        for (auto it:MAP)
        {
            if (it.second == 0)
            {
                cout << it.first+1 << "\n";
                break;
            }
        }
    }
}

//ITSA 202404 #2
//Dr. SeanXD
標籤

相關文章

發佈留言