🔗 🟢 2582. Pass the Pillow 1278

tags: `Weekly Contest 335` `數學(Math)` `模擬(Simulation)`

題意

有 $n$ 個人排成一排，編號為 $1$ 到 $n$ 。隊伍最前面的人一開始手裡握著一個枕頭。每過一秒，拿著枕頭的人就會把它傳給隊伍中的下一個人。當枕頭到達隊伍盡頭時，方向就會改變，人們會開始反方向傳遞枕頭。

例如，當枕頭到達第 $n$ 個人時，他會把它傳給第 $n - 1$ 個人，然後是第 $n - 2$ 個人，依此類推。

給定兩個正整數 $n$ 和 $time$ ，請返回經過 $time$ 秒後，拿著枕頭的人的編號。

約束條件

$2 \leq n \leq 1000$
$1 \leq time \leq 1000$

思路：模擬(Simulation) + 數學(Math)

雖然數據範圍很小，可以直接模擬整個過程解決，但是當 $time \gg n$ 時，這種方法效率較低。為此我們可以通過數學方法來解決，而不需要實際模擬整個傳遞過程，關鍵在於找出傳遞的週期性和位置計算。

注意到枕頭從第 $1$ 人傳到第 $n$ 人需要 $n-1$ 秒，再從第 $n$ 人傳回第 $1$ 人也需要 $n-1$ 秒。因此，一個週期所需時間為 $2(n-1)$ 秒。為了找到經過 $time$ 秒後枕頭的位置，我們可以先計算出枕頭在最後一個週期的位置 $r = time \bmod 2(n-1)$ ，這樣可以避免直接模擬所有 $time$ 秒的傳遞過程。

最後根據 $r$ 的值來確定枕頭的最終位置：

如果 $r < n$ ，說明枕頭還在從第 $1$ 人到第 $n$ 人的過程中，最終位置為 $1 + r$ 。
如果 $r \geq n$ ，說明枕頭已經開始反向傳遞，最終位置為 $n - (r - (n - 1)) = 2 \times n - r - 1$ 。

複雜度分析

時間複雜度： $O(1)$ 。無論輸入的 $n$ 和 $time$ 如何，都只需要進行幾次簡單的數學運算即可得到結果。
空間複雜度： $O(1)$ 。只使用了幾個變量來存儲中間結果，不需要額外的資料結構。

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        k = 2 * (n - 1) # 傳遞一圈的時間
        r = time % k
        return 1 + r if r < n else n - (r - (n - 1))

class Solution {
public:
    int passThePillow(int n, int time) {
        time %= (n - 1) << 1;
        return time < n ? 1 + time : (n << 1) - time - 1;
    }
};