c312 - PD:死亡之塔

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個約瑟夫斯問題的變體。n 個人圍成一圈，從 1 開始順時針報數，報到 k 的人被淘汰，直到只剩一個人為止。要求計算倖存者的編號。

解題思路

這題是經典的約瑟夫斯問題。由於 n 的範圍不大 (n <= 100000)，可以直接模擬整個過程。程式碼從 2 開始迭代到 n，每次計算當前倖存者的編號。ans = (ans + k) % i 模擬了報數和淘汰的過程。最後，ans + 1 得到倖存者的原始編號。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,k;
	while(cin >> n >> k){
		int ans=0;
		for(int i=2;i<=n;++i)
			ans=(ans+k)%i;
		cout << ans+1 << "\n";
	}
}